[논문]움직임벡터차에 기반한 고속 움직임 추정 방법

강현수

doi:10.5392/jkca.2011.11.5.009

[국내논문] 움직임벡터차에 기반한 고속 움직임 추정 방법
Fast Motion Estimation Method Based on Motion Vector Differences 원문보기

한국콘텐츠학회논문지 = The Journal of the Korea Contents Association, v.11 no.5, 2011년, pp.9 - 14

초록
AI-Helper

본 논문은 움직임벡터차의 확률을 이용하여 움직임 탐색 범위를 결정하는 새로운 고속 움직임 추정 방법을 제안한다. 제안된 방법은 일종의 적응적 탐색영역 방법이다. 움직임벡터차의 분포에 대한 조사하고 그 분포의 파라미터를 최대우도추정방법으로 추정한다. 이 추정된 분포를 이용하여 탐색 범위는 움직임벡터차의 지정된 확률에 의해 효과적으로 제한될 수 있음을 보인다. 실험적으로 제안된 방법의 성능이 화질면에서 전역탐색법과 유사하며 복잡도 면에서는 중대한 감소를 입증하였다. 뿐만 아니라, 제안된 방법이 기존의 적응적 탐색영역 방법에 비해 훨씬 더 효과적으로 탐색영역을 결정함을 보여주었다.

Abstract ▼ AI-Helper

This paper presents a new fast motion estimation method where search ranges are determined by the probabilities of motion vector differences (MVDs), which is an adaptive/dynamic search range (ASR) method. The MVDs' distribution is investigated and its parameter is estimated by the maximum likelihood estimator. With the estimated distribution, we show that the search ranges can be efficiently restricted by a prefixed probability for MVDs. Experimental results showed that the performance of the proposed method is very similar to that of the full search algorithm in PSNR but it enables significant reduction in the computational complexity. In addition, they revealed that the proposed method determine the search ranges much more efficiently than the conventional ASR methods.

Keyword

AI 본문요약
AI-Helper

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

문제 정의

본 논문에서는 H.264/AVC에 적용 가능한 ASR 방법에 기반한 고속 추정 방법을 제안한다. 우선, 최대우도 추정법 (maximum likelihood estimation)을 이용하여 움직임 벡터차의 확률밀도함수 (probability density func용하여 움직PDF)가 모델링된다.
이제 MVD의 분포에 대해서 살펴보자. H.
이제 적중확률에 따른 탐색범위 제한에 대해 살펴보자. 여기서 적중확률이란 MVD가 각 방향에 대해 제한된 탐색범위 [± k_x , ± k_y ] 내에 있을 사건 A와 사건 B의 확률을 의미한다.
지금까지 MVD의 PDF와 적중 확률에 대해 기술하였다. 실제적인 문제로서, 추정 벡터 #을 얻기 위해서는 N개의 MVD 샘플이 필요로 한다.
본 논문은 x와 y방향의 탐색범위를 MVD의 확률에 기반하여 효과적으로 제한함으로써 움직임 추정 계산량을 크게 감소시킬 수 있는 새로운 방법을 제안하였다. MVD의 PDF를 실험에 근거하여 라플라스분포로 가정하고, 이 PDF의 파라미터를 최대우도추정법에 의해 구하였다.

가설 설정

[3] 최종 탐색범위는 최소 탐색 범위 f를 보장할 수 있도록 재조정된다. 즉,
본 논문은 x와 y방향의 탐색범위를 MVD의 확률에 기반하여 효과적으로 제한함으로써 움직임 추정 계산량을 크게 감소시킬 수 있는 새로운 방법을 제안하였다. MVD의 PDF를 실험에 근거하여 라플라스분포로 가정하고, 이 PDF의 파라미터를 최대우도추정법에 의해 구하였다. 또한 이 PDF를 기반으로 탐색범위를 지정하였을 때 최적 움직임 벡터가 이 영역에 포함될 적중확률을 정의하였다.

제안 방법

우선, 최대우도 추정법 (maximum likelihood estimation)을 이용하여 움직임 벡터차의 확률밀도함수 (probability density func용하여 움직PDF)가 모델링된다. 이 모델링된직 PDF를 기반으로 움직임 벡터차가 탐색영역에 포함될 확률을 제한조건으로 설정함으로써 움직임 탐색영역을 결정하는 방법을 제안한다.
참고문헌 [8]과 [11]에서 설정한 QP와 동일하게 QP = 8, 18, 28, 38로 설정하여 실험하여 BDPSNR [17]을 측정하였다. [표 1]은 전역탐색법 대비 제안된 방법의 성능을 보여주고 있다.
[표 1]은 전역탐색법 대비 제안된 방법의 성능을 보여주고 있다. 또한 기존의 ASR 방법과의 비교를 위하여 Xu의 방법 [11]을 구현하여 그 결과를 [표 1]에 포함시켰다 (표에서 DSR로 표기). 표에 나타난 복잡도 (CPX)는 전역탐색법의 탐색점 수와 비교하는 방법에서 사용한 탐색점 수의 비를 의미한다.
MVD의 PDF를 실험에 근거하여 라플라스분포로 가정하고, 이 PDF의 파라미터를 최대우도추정법에 의해 구하였다. 또한 이 PDF를 기반으로 탐색범위를 지정하였을 때 최적 움직임 벡터가 이 영역에 포함될 적중확률을 정의하였다. 이 정의를 이용하여 역으로 적중확률을 제한조건으로 주었을 때 얻어지는 탐색범위를 수학적으로 유도하였다.
또한 이 PDF를 기반으로 탐색범위를 지정하였을 때 최적 움직임 벡터가 이 영역에 포함될 적중확률을 정의하였다. 이 정의를 이용하여 역으로 적중확률을 제한조건으로 주었을 때 얻어지는 탐색범위를 수학적으로 유도하였다. 그 결과 제안된 알고리즘은 총 7가지의 영상시퀀스에 대해 실험함으로써 그 성능을 평가하였다.
이 정의를 이용하여 역으로 적중확률을 제한조건으로 주었을 때 얻어지는 탐색범위를 수학적으로 유도하였다. 그 결과 제안된 알고리즘은 총 7가지의 영상시퀀스에 대해 실험함으로써 그 성능을 평가하였다.
한편, 각 영상시퀀스에 대해 네 가지 종류의 적중확률에 대해 실험을 실시하여 제안된 방법의 복잡도와 화질 사이의 관계를 알아보았다. 적중확률을 높일 경우 복잡도가 증가하는 반면 화질을 개선되는 특성을 보였으나 적중확률의 증가에도 불구하고 화질이 포화되는 현상을 발견하였다.

대상 데이터

샘플의 선정에 있어서, 주변 블록들의 움직임 정보를 이용한 수많은 선택 방법이 존재하지만, 추정 벡터가 가능하면 정확히 얻어질 수 있도록 선정에 주의하여야 한다. 메모리 요구량과 실험적인 결과를 바탕으로 총 8가지의 샘플 벡터로 구성된 집합 S₈를 선정하였다.
2 [16]에 탑재하여 실험을 수행하였다. 4개의 CIF 영상과 3개의 4CIF 영상에 대해 실험을 수행하였다. 가능한 많은 움직임이 포함될 수 있도록 CIF 이상의 해상도를 가진 영상을 선택하였다.
4개의 CIF 영상과 3개의 4CIF 영상에 대해 실험을 수행하였다. 가능한 많은 움직임이 포함될 수 있도록 CIF 이상의 해상도를 가진 영상을 선택하였다. 부호화 파라미터는 다음과 같다.

이론/모형

264/AVC에 적용 가능한 ASR 방법에 기반한 고속 추정 방법을 제안한다. 우선, 최대우도 추정법 (maximum likelihood estimation)을 이용하여 움직임 벡터차의 확률밀도함수 (probability density func용하여 움직PDF)가 모델링된다. 이 모델링된직 PDF를 기반으로 움직임 벡터차가 탐색영역에 포함될 확률을 제한조건으로 설정함으로써 움직임 탐색영역을 결정하는 방법을 제안한다.
제안된 방법의 성능 평가를 위하여 제안된 방법을 JM16.2 [16]에 탑재하여 실험을 수행하였다. 4개의 CIF 영상과 3개의 4CIF 영상에 대해 실험을 수행하였다.

성능/효과

반면 복잡도는 증가하게 된다. CIF 영상들에 대해서는 제안된 방법이 90% 이상의 계산량 감축 효과를 보여주고 있으며, 보다 넓은 탐색범위를 필요로 하는 4CIF 영상들에 대해서는 보다 많은 계산량 감축 효과를 얻을 수 있음을 관찰할 수 있다 ([표 1]의 SR=32의 행 참조). 넓은 탐색범위의 경우 제안된 방법은 입력 영상의 움직임 크기에 적응적으로 탐색범위를 조절함으로써 쓸데없는 계산량 낭비를 막아줌을 알 수 있다.
즉, Xu의 방법은 움직임이 적은 Hall-monitor 영상에 대해서는 비교적 낮은 계산량을 유지하지만 보다 큰 움직임의 가진 coastguard, foreman, stefan 영상에 대해서는 계산량이 급격히 증가함을 알 수 있다. 이에 비해 제안된 방법은 비교적 적은 량의 계산량 증가로 충분한 화질을 제공함을 알 수 있다.
전체적으로 제안된 방법은 기존의 방법에 비해 움직임이 큰 영상에서 더욱 더 우수한 결과를 얻었으며, 기존 방법의 복잡도를 약 50% 정도 감축하는 것으로 분석되었다. 움직임이 작은 영상에 대해서 제안된 방법은 기존의 방법에 비해 복잡도를 효과적으로 감축함을 알 수 있었다.
전체적으로 제안된 방법은 기존의 방법에 비해 움직임이 큰 영상에서 더욱 더 우수한 결과를 얻었으며, 기존 방법의 복잡도를 약 50% 정도 감축하는 것으로 분석되었다. 움직임이 작은 영상에 대해서 제안된 방법은 기존의 방법에 비해 복잡도를 효과적으로 감축함을 알 수 있었다.
기존의 Xu의 방법과 비교해 보면, 제안된 방법이 이 방법보다 우수한 성능을 보일 뿐만 아니라 입력영상의 움직임 특성에 잘 적응함으로써 급격한 계산량 증가를 막아줌을 알 수 있다. 즉, Xu의 방법은 움직임이 적은 Hall-monitor 영상에 대해서는 비교적 낮은 계산량을 유지하지만 보다 큰 움직임의 가진 coastguard, foreman, stefan 영상에 대해서는 계산량이 급격히 증가함을 알 수 있다.

후속연구

적중확률을 높일 경우 복잡도가 증가하는 반면 화질을 개선되는 특성을 보였으나 적중확률의 증가에도 불구하고 화질이 포화되는 현상을 발견하였다. 따라서 영상의 특성에 따라서 적절한 적중확률을 설정하는 방법의 연구가 추가적으로 요구된다.

질의응답

핵심어	질문	논문에서 추출한 답변
	ASR 방법은 무엇을 감축할 수 있는가?	한편, ASR 방법들은 시스토릭 어레이 (stytolic array)와 같은 규칙적인 구조에 의해 구현될 수 있으므로 하드웨어 친화적인 특성을 가진다. 또한 이 방법은 모든 탐색영역의 화소를 읽어올 필요가 없으므로, 외부 프레임 메모리에서 움직임 추정 모듈의 내부 메모리로의 데이터를 읽어오는데 필요한 클럭수에 해당하는 메모리 대역폭 (memory bandwidth)을 감축할 수 있다. ASR 방법들은 일반적으로 주변 블록들의 움직임 벡터의 평균, 중간 값 등의 연산을 통해 현재 블록의 움직임 탐색영역을 결정한다 [9-12].
	움직임 추정에서 계산량을 감축하기 위해 제안된 방법에는 무엇이 있는가?	그러나 움직임 추정은 많은 계산량을 요구하며, 특히 전역탐색법 (full search method)은 최적의 움직임 벡터를 찾는 반면 가장 많은 계산량이 필요하다. 계산량을 감축하기 위하여, 3단계 탐색 [2], 4단계 탐색 [3], 다이아몬드 탐색[4][5], 육각형기반 탐색 [6-8], 적응적 탐색영역 (adaptive search range: ASR) 방법 [9-14] 등 많은 고속화 방법이 제안되었다. 참고문헌 [2-8]에서 제안된 방법들은 그들 고유의 탐색 패턴을 특징으로 하면서도 탐색점의 표본화를 통해 탐색점의 개수를 감소시켜 계산량을 감축하는 공통적인 특성을 가지고 있다.
	전역탐색법의 장단점은 무엇인가?	264/AVC [1]와 같은 부호화 표준에 널리 채용되어왔다. 그러나 움직임 추정은 많은 계산량을 요구하며, 특히 전역탐색법 (full search method)은 최적의 움직임 벡터를 찾는 반면 가장 많은 계산량이 필요하다. 계산량을 감축하기 위하여, 3단계 탐색 [2], 4단계 탐색 [3], 다이아몬드 탐색[4][5], 육각형기반 탐색 [6-8], 적응적 탐색영역 (adaptive search range: ASR) 방법 [9-14] 등 많은 고속화 방법이 제안되었다.

참고문헌 (17)

ITU-T VCEG and ISO/IEC MPEG, Advanced video coding for generic audiovisual services, ITU-T Recommendation H.264 and ISO/IEC 14496-10 (MPEG-4 AVC), 2003(5).
J. Jain and A. Jain, "Displacement measurement and its application in interframe image coding," IEEE Trans. on Communications, Vol.29, No.12, pp.1799-1808, 1981(12).

상세보기
L.-M. Po and W.-C. Ma, "A novel four-step search algorithm for fast block motion estimation," IEEE Trans. on Circuits and Systems for Video Technology, Vol.6, No.3, pp.313-317, 1996(6).

상세보기
S. Zhu and K.-K. Ma, "A new diamond search algorithm for fast block matching motion estimation," IEEE Trans. on Image Processing, Vol.9, No.2, pp.287-290, 2000(2).

상세보기
C. Cheung and L. Po, "A Novel Cross-Diamond Search Algorithm for Fast Block Motion Estimation," IEEE Trans. on Circuits and Systems for Video Technology, Vol.12, No.12, pp.1168-1177, 2002(12).

상세보기
C. Zhu, X. Lin, and L. P. Chau, "Hexagon-based search pattern for fast block motion estimation," IEEE Trans. on Circuits and Syst. Video Technol., Vol.12, No.5, pp.349-355, 2002(5).

상세보기
Z. Chen, P. Zhou, and Y. He, Fast integer and fractional pel motion estimation for JVT, JVT-F017r, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, 2002(12).
X. Yi, J. Zhang, N. Ling, and W. Shang, Improved and simplified fast motion estimation for JM, JVT-P021, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, 2005(7).
M.-C. Hong and H. H. Oh, Range decision for motion estimation of VCEG-N33, JVT-B022, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, Feb. 2002.
M.-C. Hong, Chul-Woo Kim, and Kyoung Seok In, Further improvement of motion search range, JVT-D117, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, 2002(7).
X. Xu, Y. He, Modification of dynamic search range for JVT, JVT-Q088, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, 2005(10).
T. Song, K. Ogata, K. Saito, and T. Shimamoto, "Adaptive search range motion estimation algorithm for H.264/AVC," Proc. of International Symposium on Circuits and Systems, pp.3956-3959, 2007.
S. W. Lee, S. M. Park, and H. S. Kang, "Fast motion estimation with adaptive search range adjustment," Optical Engineering, Vol. 46, No. 4, pp. 040504-1-040504-3, 2007(4).

상세보기
Z. Chen, Y. Song, T. Ikenaga, and S. Goto, "A macroblock level adaptive search range algorithm for variable block size motion estimation in H.264/AVC, "Proc. of Int. Sym. on Intelligent Signal Processing and Comm. Sys., pp.598-601, 2007.
K.-P. Lim, G. Sullivan, and T. Wiegand, Text description of joint model reference encoding methods and decoding concealment methods, JVT-N046, Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG, 2005(1).
H.264/AVC Reference Software JM16.2, http://iphome.hhi.de/suehring/tml/download/
K. Andersson, R Sjoberg, and A. Norkin, Reliability measure for BD measurements, ITU-T SG16 Q.6 Document, VCEG-AL22, 2009(7).

저자의 다른 논문 :

표제어: 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

연합인증