[논문]H.264 움직임 추정을 위한 효율적인 SAD 프로세서

장영범; 오세만; 김비철; 유현중

[국내논문] H.264 움직임 추정을 위한 효율적인 SAD 프로세서
Efficient SAD Processor for Motion Estimation of H.264 원문보기

電子工學會論文誌. Journal of the Institute of Electronics Engineers of Korea. SP, 신호처리, v.44 no.2 = no.314, 2007년, pp.74 - 81

장영범 (상명대학교 정보통신공학과) , 오세만 (상명대학교 정보통신공학과) , 김비철 (상명대학교 정보통신공학과) , 유현중 (상명대학교 정보통신공학과)

초록
AI-Helper

이 논문에서는 H.264의 효율적인 움직임 추정을 위한 새로운 SAD(Sum of Absolute Differences) 프로세서의 구조를 제안하였다. SAD 프로세서는 전영역 탐색기법의 움직임 추정이나 고속 탐색기법의 움직임 추정에서 모두 사용되는 중요한 블록이다. 제안된 구조는 SAD 계산기 블록, combinator 블록, 최소값 계산기 블록의 3개의 블록으로 구성된다. 제안된 구조는 덧셈연산을 분산 연산(Distributed Arithmetic)을 사용하여 계산함으로써 구조를 단순화시켰다. 제안 구조를 HDL(Hardware Description Language)을 사용하여 실험한 결과 기존의 구조와 비교하여 39%의 게이트 카운트 감소효과를 보였다. 또한 FPGA를 사용하여 검증한 결과도 32%의 게이트 카운트 감소효과를 보였다. 따라서 제안된 움직임 추정용 SAD 프로세서는 칩의 면적이 중요한 변수인 H.264 칩에서 널리 사용될 수 있는 구조가 될 것이다.

Abstract ▼ AI-Helper

In this paper, an efficient SAD(Sum of Absolute Differences) processor structure for motion estimation of H.264 is proposed. SAD processors are commonly used both in full search methods for motion estimation and in fast search methods for motion estimation. Proposed structure consists of SAD calculator block, combinator block, and minimum value calculator block. Especially, proposed structure is simplified by using Distributed Arithmetic for addition operation. The Verilog-HDL(Hard Description Language) coding and FPGA(Field Programmable Gate Array) implementation results for the proposed structure show 39% and 32% gate count reduction in comparison with those of the conventional structure, respectively. Due to its efficient processing scheme, the proposed SAD processor structure can be widely used in size dominant H.264 chip.

주제어

AI 본문요약
AI-Helper

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

문제 정의

이 논문에서는 4×4 SAD 계산기를 16개 사용하여 고속으로 SAD를 계산하는 방식을 제안한다. 16개의 4×4 SAD 계산기를 사용하므로 각각의 4×4 SAD 계산기의 하드웨어 구조를 작게 하는 것이 이 논문의 핵심이다.
본 논문에서는 H.264 움직임 주정 알고리즘에 사용되는 SAD 연산을 위한 단순화된 구조를 제안하였다. 제안된 SAD 프로세서는 SAD 계산기, Combinator, 최소값 계산기로 구성하였으며 특히 분산 연산을 사용하여 SAD 계산기의 게이트 카운트를 줄일 수 있었다.
또한 그 중간인 4개의 4×4 SAD 계산기를 만들어서 4번 반복하여 사용할 수도 있다. 이 논문에서는 4×4 SAD 계산기를 16개 사용하여 고속으로 SAD를 계산하는 방식을 제안한다. 16개의 4×4 SAD 계산기를 사용하므로 각각의 4×4 SAD 계산기의 하드웨어 구조를 작게 하는 것이 이 논문의 핵심이다.

제안 방법

이렇게 비트를 순차적으로 연산하게 되어 총 13 클록 후에 SAD 값이 출력된다. 1개의 SAD 계산기는 16개의 AD 값과 1개의 SAD 값을 만들도록 실험하였다. 따라서 16×16의 마크로 블록에 대하여 제안된 구조는 16개의 SAD 값들을 동시에 출력하도록 실험하였다.
그 결과 값의 MSB를 검사하여。이면, 즉 양수이면 MU以의 sei이 0이 되어 값을 그대로 통과시키게 설계하였다. 그리고 MSB가 1이면, 즉 결과 값이 음수이면 절대값을 계산하기위하여 인버터회로와 +1회로를 거치도록 설계하였다. 이 동작이 직렬로 동작하므로 A2의 +1회로는 반가산기 1개로 구성할 수 있다.
기존의 SAD 방식 계산기 구조와 비교하여 우리는 16개의 operand를 LSB부터 더하는 방식을 제안한다. 즉, 16개의 AD 값들을 병렬로 받아서 LSB의 1비트부터 계산하는 방식이다.
세 번째 클록에 11 비트의 가산기를 2개 사용하고 2개의 12 비트 레지스터에 저장된다. 네 번째 클록에 12 비트의 가산기를 1개 사용하고 1개의 13 비트 레지스터에 저장되어 4×4 블록의 SAD 값이 출력되도록 실험하였다.
세 번째 클록에 3 비트의 가산기를 2개 사용되고 2개의 4 비트 레지스터에 결과 값을 저장하였다. 네 번째 클록에 4 비트의 가산기를 1개 사용하고 1개의 5 비트 레지스터에 결과를 저장하였다. 다섯 번째 클록에 먼저 저장되어있던 값을 LSB 쪽(right shift)으로 1 비트 쉬프트 하고 현재 출력된 5 비트의 값과 덧셈을 수행하였다.
네 번째 클록에 4 비트의 가산기를 1개 사용하고 1개의 5 비트 레지스터에 결과를 저장하였다. 다섯 번째 클록에 먼저 저장되어있던 값을 LSB 쪽(right shift)으로 1 비트 쉬프트 하고 현재 출력된 5 비트의 값과 덧셈을 수행하였다. 이렇게 비트를 순차적으로 연산하게 되어 총 13 클록 후에 SAD 값이 출력된다.
제안구조는 처음 클록에 1 비트의 가산기가 8개 사용되고 8개의 2 비트 레지스터에 저장하였다. 두 번째 클록에는 2 비트의 가산기를 4개 사용하고 4개의 3 비트 레지스터에 저장하였다. 세 번째 클록에 3 비트의 가산기를 2개 사용되고 2개의 4 비트 레지스터에 결과 값을 저장하였다.
본 논문에서 제안한 4×4 SAD 프로세서의 성능을 평가하기 위해 Verilog-HDL시뮬레이션을 수행하였다. 실험에 사용된 To이은 Xilinx ISE 7.
41개의 Combination 블록 출력 값은 다음 새로운 값이 입력 될 때까지 레지스터에 저장하였다. 이와 같이 계산된 새로운 41개의 Combination 블록 출력 값이 최소값 계산기 블록으로 입력되면 기존에 저장되어 있던 값과 비교하여 더 작은 값을 다시 저장하도록 하였다. 이와 같은 연산을 반복하여 가장 작은 출력 값의 위치벡터인 8 비트의 움직임 벡터 값을 출력하게 된다.
SAD 계산기의 저전력 구조이다. 즉, 4×4 SAD 계산을 위한 저전력 구조를 제안하며, 이를 16개 사용하여 4×4 SAD 계산기 구조를 설계하였다. 제안된 전체의 SAD 프로세서 구조는 다음과 같이 3개의 파트로 구성된다.
기존의 SAD 방식은 1단계에 8개의 가산기를 필요로 한다. 즉, ADO과 ADI, AD2와 AD3, AD4와 AD5, AD6 과 AD7, AD8 과 AD9, AD10 과 AD11, AD12와 AD13, AD14와 AD15를 각각 가산기를 사용하여 더한다. 따라서 2단계에는 4개, 3단계에는 2개 마지막 4단계에 1개의 가산기를 필요로 한다.

대상 데이터

실험에 사용된 To이은 Xilinx ISE 7.1i이고, 입력샘플로 그림 8과 같은 순차적인 2프레임의 QCIF급 "foreman” 영상을 사용하였다. 움직임 벡터의 범위는 (T6, -16广 (15, 15)를 사용하였다.
따라서 16×16의 마크로 블록에 대하여 제안된 구조는 16개의 SAD 값들을 동시에 출력하도록 실험하였다. 16개의 13 비트 정세 도의 SAD 값들을 Combination 블록의 입력으로 사용하였다. 즉, Combination 블록으로 입력된 16개의 4×4 SAD 값들을 조합하여 4x8, 8x4, 8×8, 16x8, 8x16,16×16 등의 크기의 총 41 개의 SAD 값을 만들어 냈다.
1개의 SAD 계산기는 16개의 AD 값과 1개의 SAD 값을 만들도록 실험하였다. 따라서 16×16의 마크로 블록에 대하여 제안된 구조는 16개의 SAD 값들을 동시에 출력하도록 실험하였다. 16개의 13 비트 정세 도의 SAD 값들을 Combination 블록의 입력으로 사용하였다.
우리가 제안하는 핵심 하드웨어는 첫 번째 블록인 4×4 SAD 계산기의 저전력 구조이다. 즉, 4×4 SAD 계산을 위한 저전력 구조를 제안하며, 이를 16개 사용하여 4×4 SAD 계산기 구조를 설계하였다.
제안한 구조는 그림 7의 최소값 계산기를 41개 사용한다. 그림 7에서 Reg.
16개의 13 비트 정세 도의 SAD 값들을 Combination 블록의 입력으로 사용하였다. 즉, Combination 블록으로 입력된 16개의 4×4 SAD 값들을 조합하여 4x8, 8x4, 8×8, 16x8, 8x16,16×16 등의 크기의 총 41 개의 SAD 값을 만들어 냈다. 41개의 Combination 블록 출력 값은 다음 새로운 값이 입력 될 때까지 레지스터에 저장하였다.
두 번째 파트인 Combination 블록에서는 4×4 SAD들을 조합하여 더 큰 크기의 SAD들을 계산한다. 즉, H.264에서 필요한 41가지의 SAD들을 만들어낸다. 마지막으로 세 번째 파트인 최소값 계산기에서는 각각의 블록크기에 대한 최소 SAD를 비교하여 탐색영역 내의 가장 작은 값을 골라내는 작업을 수행한다.

성능/효과

그 결과 총상대면적은 기존구조가 1160이고 제안구조가 462로 예상된다. 따라서 제안 구조의 4×4 SAD 연산기와 기존 구조를 비교하였을 때 60.2%의 면적 감소가 예상된다.
제안 구조의 SAD 계산기는 기존구조에 비해 39%의 면적감소 효과를 얻을 수 있었고, 전체 SAD 프로세서 구조는 기조 구조와 비교하여 32%의 게이트 카운트 감소 효과를 달성하였다.
제안된 SAD 프로세서는 SAD 계산기, Combinator, 최소값 계산기로 구성하였으며 특히 분산 연산을 사용하여 SAD 계산기의 게이트 카운트를 줄일 수 있었다. 제안된 SAD 프로세서 구조에 대한 FPGA 실험 결과 게이트 카운트를 32% 감소시킬 수 있었다. 따라서 제안된 움직임 추정용 SAD 프로세서는 구현 면적을 중요한 변수로 설계하는 경우의 H.
264 움직임 주정 알고리즘에 사용되는 SAD 연산을 위한 단순화된 구조를 제안하였다. 제안된 SAD 프로세서는 SAD 계산기, Combinator, 최소값 계산기로 구성하였으며 특히 분산 연산을 사용하여 SAD 계산기의 게이트 카운트를 줄일 수 있었다. 제안된 SAD 프로세서 구조에 대한 FPGA 실험 결과 게이트 카운트를 32% 감소시킬 수 있었다.
표 2 에서 보듯이 기존 구조와 비교하여 전가산기의 수가 3기개에서 138개로 감소되었으며, 반가산기의 수는 47개에서 48개로 1개가 증가하였다. 위의 표에서 상대 면적의 계산은 반가산기 1개의 면적을 1로 정의하고 전가산기의 상대면적은 반가산기의 3배로 정의하였다.
표 3에서 보듯이 기존구조의 게이트 카운트는 8, 011 이며, 제안구조는 4, 912로서 39%의 게이트 카운트 감소를 달성하였다.

후속연구

제안된 SAD 프로세서 구조에 대한 FPGA 실험 결과 게이트 카운트를 32% 감소시킬 수 있었다. 따라서 제안된 움직임 추정용 SAD 프로세서는 구현 면적을 중요한 변수로 설계하는 경우의 H.264 칩에서 널리 사용될 수 있을 것이다.

참고문헌 (10)

Draft ITU-T recommendation and final draft International Standard of Joint Video Specification (ITU-T Rec. H.264/ISO/IEC 14496-10 AVC) JVT-G050, Geneva, Switzerland, 23-27, May 2003
S. Y. Yap and J.V. McCanny, 'A VLSI Architecture for Variable Block Size Video Motion Estimation', IEEE Trans. on Circuits and Systems II: Express Briefs, Vol. 51, issue 7, pp. 384-389, Jul. 2004

상세보기
Y. W. Huang, T.C. Wang, B.Y. Hsieh, and L. G. Chen, 'Hardware Architecture Design for Variable Block Size Motion Estimation in MPEG-4 AVC/JVT/ITU-T H.264', Proceedings of the 2003 International Symposium on Circuits and Systems, Vol. 2, pp. 796-799, May 2003
C. Y. Kao and Y. L. Lin, 'An AMBA-Compliant Motion Estimator for H.264 Advanced Video Coding', Proceedings of 2004 International Conference on SOC Design, Vol.1, pp. 117-120, Oct. 2004
C. Y. Cho, S. Y. Huang, and J. S. Wang, 'An Embedded Merging Scheme for H.264/AVC Motion Estimation', Proceedings of International Conference on Image Processing, Vol. 1, pp. 909-912, Sep. 2003
S. Zhu and K. Ma, 'A new diamond search algorithm for fast block matching', IEEE Trans. on Image Proc., Vol. 9, No. 2, pp.287-290, Feb. 2000

상세보기
P. Hosur and K. Ma, 'Motion vector field adaptive fast motion estimation', Second International Conference on Information, Communication and Signal Processing (ICICS '99), Singapore, pp. 7-10, Dec. 1999
A. Tourapis, O. Au, and M. Liou, 'Highly efficient predictive zonal algorithms for fast block-matching motion estimation', IEEE Trans. on Circuits and Systems for Video Technology, pp. 934-947, Oct. 2000
Donghyung Kim, Jechang Jeong, Xiao Song and Chengke Wu, 'A Fast Macroblock Mode Selection Algorithm In The H.264/AVC Standard,' IWAIT 2005, pp.157-162, Jan. 2005
Chen-Fu Lin, Jin-Jang Leou, 'Adaptive Fast Full Search Motion Estimation Algorithm for H.264,' IEEE International Symposium on Circuits and Systems, pp.1493-1496, May 2005

저자의 다른 논문 :

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

연합인증