66 다양한블록크기의전역탐색알고리즘을위한효율적인구조를갖는움직임추정기설계황종희외 논문 2009-46SD-11-9 다양한블록크기의전역탐색알고리즘을위한 효율적인구조를갖는움직임추정기설계 (The Motion Estimator Implementation with Efficient Structure for Full Search Algorithm of Variable Block Size ) 황종희 *, 최윤식 * * (Jonghee Hwang and Yoonsik Choe ) 요 약 움직임추정은영상부호화시스템에서큰비중을차지하는부분으로, 실시간동작을위해서는효율적인구조를필요로한다. 따라서 H.264 전체시스템을위한움직임추정기블록의구현은부호화과정을고속으로수행할수있도록별도의전용하드웨어모듈로설계하는것이바람직하다. 본논문에서는많은연산량을효율적으로줄일수있도록병렬처리를바탕으로움직임추정감지블록, 41 개의 SAD(Sum of Absolute Difference) 값계산블록, 최소의 SAD 값계산과움직임벡터생성블록을제안하고자한다. 움직임추정감지블록과최소의 SAD 값계산기에서는선계산 (pre-computation) 방법을적용함으로써, 입력 Switching Activity 를줄여고속구현이가능하도록하였으며, 움직임추정감지블록과 41 개의 SAD 값계산블록에서가장많은부분을차지하는가산기구조를일반적으로사용되는 Ripple Carry Adder 대신에 Carry Skip Adder 를적용함으로써, Adder Tree 구조를고속으로처리할수있도록하였다. 또한외부에서탐색영역제어와같은주요변수를쉽게제어할수있도록하여, 하드웨어구조의효율성을높였다. 시뮬레이션및 FPGA 검증결과, 움직임추정기의임계경로를발생시키는 MED 블록에서일반적인구조를적용했을때보다 19.89% 의 Delay 감소효과를얻을수있었다. Abstract The motion estimation in video encoding system occupies the biggest part. So, we require the motion estimator with efficient structure for real-time operation. And for motion estimator's implementation, it is desired to design hardware module of an exclusive use that perform the encoding process at high speed. This paper proposes motion estimation detection block(med), 41 SADs(Sum of Absolute Difference) calculation block, minimum SAD calculation and motion vector generation block based on parallel processing. The parallel processing can reduce effectively the amount of the operation. The minimum SAD calculation and MED block uses the pre-computation technique for reducing switching activity of the input signal. It results in high-speed operation. The MED and 41 SADs calculation blocks are composed of adder tree which causes the problem of critical path. So, the structure of adder tree has changed the most commonly used ripple carry adder(rca) with carry skip adder(csa). It enables adder tree to operate at high speed. In addition, as we enabled to easily control key variables such as control signal of search range from the outside, the efficiency of hardware structure increased. Simulation and FPGA verification results show that the delay of MED block generating the critical path at the motion estimator is reduced about 19.89% than the conventional strukcture. Keywords : motion estimation detection, SAD, pre-computation, carry skip adder Ⅰ. 서론 * 정회원, 연세대학교, 전기전자공학과 (Dept., Electrical & Electronics Eng. Yonsei University) 접수일자 : 2009년9월1일, 수정완료일 : 2009년10월23일 디지털멀티미디어방송에사용되는 H.264는압축효율이나영상의화질측면에있어서기존의표준보다 (954)
2009 년 11 월전자공학회논문지제 46 권 SD 편제 11 호 67 뛰어난성능을보이지만, 그에따라부호화과정의복잡도나부호화시간이훨씬증가하여비디오영상의실시간처리가어렵다. 특히움직임예측및보상과정은영상부호화시스템에서큰비중을차지하는부분이며, 차세대코덱으로불리는 H.265에서도움직임추정 (motion estimation) 을수행하는부분은전체인코딩시스템에서가장큰연산량을가질것이다. 예를들어전역탐색알고리즘 (full search algorithm) 은가장편리하면서도가장효과적으로움직임추정을수행할수있는방법이지만다양한블록사이즈의매크로블록에대한움직임벡터를구하기위해서는허용된탐색영역내의모든픽셀에대해블록단위로 SAD(sum of absolute difference) 연산을수행해야하기때문에매우많은연산량이요구되어진다. 실제로전역탐색을통한움직임추정알고리즘은그림 1에서와같이일반적인동영상의부호화시스템에서전체연산량의 65% 이상을차지할정도로큰비중을차지하고있다. 일반적으로 구조의비디오영상에서 I 프레임을제외한 P/B 프레임은영상의화질과압축효율이움직임추정에의해많은영향을받으며, H.264에서는움직임추정의비용함수로서다음과같은 RDO(Rate Distortion Optimization) 개념을사용한다. (1) 여기서 은움직임벡터, 는예측된움직임벡터, 은라그랑제상수 (Lagrange multiplier) 를나타낸다. 는현재블록, 은움직임벡터 이가리키는참조블록을의미한다. H.264 에서는이와같이현재블록과참조블록의오차또는왜곡뿐만아니라움직임벡터의부호화율 (Bit Rate) 을함께고려하여최소비용을가지는지점을 찾는움직임예측을수행한다. 전역탐색을수행하면탐색영역내의모든블록에대해위와같은비용함수 를계산하기때문에최소의비용에해당하는블록을찾을수있다. 여기서움직임추정을위한오차 (Distortion) 측정함수로식 (2) 와같이 Mean Square Error(MSE), Sum of Absolute Difference (SAD), Mean Absolute Difference(MAD) 가존재하며, 이중에서 SAD가곱셈기와나눗셈연산이필요하지않기때문에하드웨어구현에주로사용된다. (2) 본논문에서는움직임추정알고리즘이갖는많은연산량을효율적으로감소시키면서고속처리가가능한움직임추정블록을설계하기위해서, SAD를계산하기위한픽셀연산블록들을모두병렬연산이가능하도록하였다. 또한, 전체움직임추정기를구성하는움직임추정감지블록과 41개의 SAD값계산기블록에서가장많은부분을차지하는가산기구조를일반적으로사 용되는 Ripple Carry Adder 대신에 Carry Skip Adder 를적용함으로써, Adder Tree 구조를고속으로처리할수있도록하였고, 움직임추정감지블록과최소의 SAD값계산기에서는선계산 (pre-computation) 을이용함으로써입력 Switching Activity를줄여고속구현이가능하도록하였다. 논문의구성은다음과같다. Section Ⅱ에서는전역탐색알고리즘및기존논문연구에대하여정리하였고, Section Ⅲ에서는다양한블록사이즈의전역탐색에적합한움직임추정기구조를제안하였다. Section Ⅳ에서는 Verilog HDL(Hardware Description Language) 를사용하여움직임추정기를하드웨어로구현하고, FPGA(Field Programmable Gate Array) 로검증한결과를정리하였다. Section Ⅴ에서는제안된구조의우수성을설명하면서결론을맺는다. Ⅱ. 전역탐색알고리즘및기존논문연구 그림 1. H.264 부호화기의각모듈별수행시간비율 Fig. 1. The processing time ratio of H.264 Encoder. 1. 다양한블록크기의전역탐색 움직임추정방법은 Optical flow method, (955)
68 다양한블록크기의전역탐색알고리즘을위한효율적인구조를갖는움직임추정기설계황종희외 그림 3. H.264의다양한블록사이즈 Fig. 3. The various block sizes in H.264. 그림 2. 블록정합을통한움직임추정방법 Fig. 2. The motion estimation method through block matching. Pel-recursive method, Phase correlation method, Block matching method 등으로구성되었으며, 이중에서간단한동작과하드웨어구현으로인해 Block matching method가가장널리사용되고있다 [1]. 전역탐색 block matching method는그림 2와같이현재프레임에서 N N 크기의현재블록 (current block) 에대해서이전프레임의탐색영역에서모든참조블록 (reference blocks) 과의정합을통하여정합오류가최소가되는탐색블록을찾아이를이용하여움직임벡터를추정하는방식이다. 이를수식으로표현하면아래와같다. (3) C(k,l) 과 R(i+k,j+l) 은현재프레임과참조프레임의픽셀위치에서휘도값을나타내고, Best Match는탐색영역에서최소의 SAD값을갖는움직임벡터 MV(i,j) 를나타낸다. 블록정합은두블록간의유사성을계산하는과정이고, 프레임간시간적차이가매우작기때문에두프레임은많은연관성을갖게된다. 연속된두프레임간이러한관계를 Temporal Redundancy 라고하며영상압축이란중복성을제거하는것이기때문에움직임추정은 Temporal Redundancy를제거하는과정이라고할수있다. H.264에서는가변블록움직임보상을사용하고있다. MPEG-2 에서는 16 16 화소고정크기움직임보상블록을사용하고, MPEG-4 에서는 16 16 화소와 8 8 화소두종류의움직임보상블록을사용한다. 반 면에 H.264 에서는그림 3과같이 16 16 화소로부터 4 4 화소까지 7 종류의움직임보상블록크기를사용하고있으며, 움직임추정기에서발생하는출력인 SAD 최소값과움직임벡터는 4 4 16개, 4 8 8개, 8 4 8개, 8 8 4개, 8 16 2개, 16 8 2개, 16 16 1개로총 41개로나타낼수있다. 매크로블록모드는 8 8, 8 16, 16 8, 16 16 으로, 서브매크로블록모드는 4 4, 4 8, 8 4, 8 8으로구성된다. 움직임보상의블록크기를보다작게하면보다정확한예측을할수있어, 압축효율을높일수있다. 2. 기존논문분석움직임추정을위한많은알고리즘과하드웨어관련된논문들이제안되어왔다. 연산복잡도를줄이기위해서전역탐색과는달리탐색영역내에서몇개의픽셀위치에서만탐색하거나영상의특성에따라블록을선택하는고속알고리즘이제안되었다 [2~6]. 하지만, 이와같은고속탐색알고리즘은움직임예측의시간이나비용은절약할수있을지모르지만, 영상에있어서불규칙적인메모리제어, 화질의열화, 압축율의저하등의문제로이어지게된다. 따라서전역탐색알고리즘이구조의간단함, 규칙성, 우수한화질로인해실제구현과정에서널리사용되고있다. 하드웨어관점에서는움직임추정기를구성하는단위블록들을병렬로배열하여저전력및고속처리가가능한구조가제안되었고 [7~8], 이전프레임의메모리데이터재활용을극대화하기위해서탐색영역내에서의다양한스캔방법 [9~10] 과대부분의블록정합이탐색영역원점주위에분포되어탐색되는영역을단순화시키는방법 [11~12] 들이제안되어왔다. 이와같은방법은최소의 SAD를갖는 Best Matching 블록을빠른시간내에찾게되면연산량을감소시키면서고속처리가가능하다. 그리고메모리측면에서는탐색영역에서의중첩 (956)
2009 년 11 월전자공학회논문지제 46 권 SD 편제 11 호 69 된데이터를재활용하여메모리대역폭을줄일수있는장점이있다. 본논문에서는기존에제안된메모리대역폭의효율적인제어와병렬처리를기본구조로외부인터페이스회로내장, 선계산방법적용, 움직임추정기에서대부분의연산을차지하는가산기를 Carry Skip Adder로변경적용등을통해, 하드웨어구조의효율성을향상시키면서고속처리가가능하도록하였다. Ⅲ. 제안된움직임추정기구조 1. 전체움직임추정기구조의블록도움직임추정기는크게현재프레임과참조프레임의영상데이터를저장하는외부메모리 (SDRAM), 현재프레임에서 16 16 매크로블록모드로분할한데이터와최대탐색영역의데이터를저장하는내부메모리 (SRAM), 움직임추정을위한하드웨어로직설계부, 탐색영역의크기에따라외부메모리부터로내부메모리데이터를읽어들이기위한주소생성기및데이터제어설계부, 외부에서사용자가 PC를통해주요변수를손쉽게제어할수있도록하기위해설계된 I2C(Inter Integrated Circuit) 통신용인터페이스회로부등으로구성된다. 여기서 SRAM은 FPGA에내장된형태로구현하여실시간으로데이터처리가가능하도록 하였으며, ASIC(Application Specific Integrated Circuit) 으로제작시에도 SRAM은내장되어구현될수있다. 움직임추정기에대한하드웨어설계부는 16 16 픽셀을 4 4 픽셀단위로분할하여현재픽셀과참조픽셀간의 SAD를계산하는블록, 16개 4 4 픽셀의 SAD 값을사용하여 7가지모드인 4 4, 4 8, 8 4, 8 8, 8 16, 16 8, 16 16 픽셀에대한 SAD값을계산하는블록, 모든탐색영역내에서최소의 SAD값과움직임벡터를계산하는블록으로구성된다. 위에서설명된전체구조의데이터흐름을그림 4와같이나타내었다. 움직임감지를위한메모리데이터할당방법, 움직임추정기에대한하드웨어설계부, I2C 통신을위한인터페이스회로부에대해서는다음절에서상세하게설명하였다. 2. 움직임감지를위한메모리데이터할당방법탐색영역내에서전역탐색을수행할때, 16 16 현재블록은 SRAM에서데이터를받아온후, 전역탐색이끝날때까지변경되지않는다. 그러나탐색영역내에서현재블록이한픽셀씩이동해가며 Block Matching 을진행할때, SRAM에서 16 16 픽셀에해당하는탐색영역데이터가갱신되어야한다. 여기서중복되는많은픽셀데이터를효율적으로재사용하기위하여메모리재사용방식과그림 5의화살표방향과같은스캔방법을사용하였다. 그림 5에서와같이홀수라인에서는오른쪽으로이동하고짝수라인에서는왼쪽으로이동하며탐색영역내에서현재매크로블록과의매칭을진행한다. 그리고각라인의마지막탐색지점의연산을완료하면밑으로이동하게된다. 메모리재사용방식이란입력받은영상데이터중에서 16 16 그림 4. 제안된움직임추정기의전체구조 Fig. 4. The whole architecture of proposed motion estimator. 그림 5. 탐색영역내에서 16 16 현재블록의스캔방향 Fig. 5. The scan direction of a 16 16 current block in the search range. (957)
70 다양한블록크기의전역탐색알고리즘을위한효율적인구조를갖는움직임추정기설계황종희외 픽셀단위로움직임추정후다음에입력받을탐색영역의영상데이터가동일할시새롭게영상데이터를입력받는것이아니라메모리의위치를이동하여영상데이터의입력횟수를줄이는방식이다 [12]. 위와같은방법을적용하기위해서, 그림 4에서움직임추정감지블록 (MED) 은스캔방향에따라좌 우방향으로이동할때에는탐색영역내에서 16 1 픽셀에해당하는데이터만입력받고, 연속해서 16 15 픽셀데이터를중복해서사용할수있게된다. 동일하게아래방향으로이동할때에는 1 16 픽셀에해당하는데이터만입력받고, 15 16의픽셀데이터는 MED블록에서이동되어다음연산과정에서재활용된다. 따라서사용되는 SRAM은실시간처리가가능하도록 16개로나누어클럭마다탐색영역내에서 16 16 매크로블록과정합될새로운데이터인 1 16 또는 16 1의데이터를읽어들일수있도록하였다. 즉, 각각의 SRAM은하나의픽셀에대한 8비트데이터버스를통해출력하고, MED 블록에서는 16개의 SRAM에서출력된 8비트데이터를묶어서총 128비트를가지고, SAD 연산을위해사용되는단위블록으로재할당되게된다. 또한이전클럭에유지하고있던픽셀데이터는 SAD를구하기위하여배열된단위블록내에서스캔방향과데이터입출력포트를통해이동되어재사용된다. 3. 움직임추정감지블록 (MED) 움직임추정감지블록은 16 16의현재블록과참조블록픽셀을 16개의 MED_X 블록에할당하여병렬처리가가능하도록하였다. 이를통해로직이차지하는면적은증가하지만, 처리시간은단축된다. MED_X 블록은다양한움직임보상의블록크기에서가장작은 4 4 SAD를계산하는역할을수행하며, 병렬로배열된 16개의 MED_X 결과가 41개의 SAD 계산블록에전달된다. 각각의 MED_X 블록은그림 6과같이 16개의 AD(Absolute Difference) 블록과 Adder Tree를갖는 32 비트입 출력포트로구성되어있으며, 4 4 픽셀에대한 SAD를계산하여출력하는역할을수행한다. 그리고 AD블록은픽셀단위의절대값연산을수행하는블록으로 8비트입 출력포트로구성되며, AD_0, 4, 8, 12는상위블록인 MED_X 블록을통해새롭게 SRAM에서탐색영역의데이터를입력으로받고이전에입력받은데이터를출력포트를통해전달하는기능을수행한다. 스캔방향에따라 SRAM 으로부터새롭게입력받는 그림 6. (a) MED_X 블록의입출력포트, (b) MED 블록 의하드웨어구조도 Fig. 6. (a) The input and output port of MED_X block, (b) Hardware structure of MED block. AD블록과기존의데이터를전달하는방향은움직임추정기에서입력되는 Select 신호에따라다르게설정된다. 만약스캔방향이오른쪽이라면, AD_0, 4, 8, 12 AD_1, 5, 9, 13 AD_2, 6, 10, 14 AD_3,7,11,15 방향으로참조픽셀의데이터가전달된다. 그러나 SRAM에서입력받은현재블록의데이터는탐색영역내에서블록매칭이끝날때까지유지된다. 가. AD 블록과 4 4 SAD Adder Tree 구조 AD 블록은현재픽셀과이전픽셀과의절대값을구하는블록으로, 입력으로받는두개의값을비교하여음의값이발생하지않도록뺄셈을수행한다. 그다음구해진 16개의차이값을입력으로 Adder Tree구조를통해 4 4 SAD값을구하게된다. 그림 7에서와같이다단으로구성된 Adder Tree는 1단에서 8개, 2단에서 4 개, 3단에서 2개, 4단에서 1개의 Ripple Carry Adder를사용하여구현된다. Ripple Carry Adder는비트단위연산을통해그다음비트연산에대한 Carry를발생하는구조로많은처리시간을필요로하며, 구조가단순하여널리사용된다. 일반적으로, 움직임추정기구조에서 MED 및 AD (958)
2009 년 11 월전자공학회논문지제 46 권 SD 편제 11 호 71 표 1. MED 블록에사용된가산기종류및개수 Table 1. Adder type and number used for MED block. 가산기종류 사용된개수 비고 8비트가산기 128(8 16) 9비트가산기 64(4 16) MED 블록은 16개의 10비트가산기 32(2 16) MED_X 블록으로구성. 11비트가산기 16(1 16) Total 240 블록정합당사용된가산기개수 그림 7. 일반적인 4 4 SAD 계산기구조 Fig. 7. The conventional structure of 4 4 SAD calculator. 블록들이모두병렬로배열되어처리될때 AD블록과 Adder Tree의데이터처리시간이하드웨어로직에대한임계경로 (Critical Path) 가된다. 따라서전체시스템의처리속도를개선하기위해서는반드시 AD블록과 Adder Tree의구조를고속처리가가능하도록최적화시켜야한다. 따라서본논문에서는첫번째로절대값을계산할때입력의일부분만으로출력을나타낼수있는입력들의부분집합을찾아내서, 이를이용하여고속으로출력될수있는선계산 (pre-computation) 기법을제안하였다. 즉, 그림 8과같이 RB-CB와 CB-RB값두가지경우에대해미리뺄셈을수행한후, 현재픽셀 (CB[7]) 과이전픽셀 (RB[7]) 의최상위비트값을비교기의입력으로받아미리예측함으로써, 양이되는출력값을선택할수있도록하였다. 만약에 CB [7] 값과 RB [7] 값이같다면기존구조와동일하게절대값을구하게된다. 위와같이제안된선계산구조는입력의 Switching Activity를줄여서고속구현을가능하게한다. 두번째로 Adder Tree에사용되는가산기를고속처리가가능한 CSA(Carry Skip Adder) 구조로변경적용하였다. 가산기는디지털회로에서가장기본적이고 그림 8. 제안된 AD 구조 Fig. 8. The proposed AD Structure. 표 2. 8/16비트가산기유형에대한상대적인비교. Table 2. Relative comparison for 8/16Bit adder type. Avg. Area(mm 2 ) Delay(ns) Adder Type Power(uW) 8 16 8 16 8 16 Ripple Carry 1 1 1 1 1 1 Carry Skip 1.23 1.45 0.82 0.60 1.15 1.06 Carry Select 1.33 1.63 0.78 0.54 1.24 1.35 Lookahead 1.41 1.61 0.74 0.54 1.24 1.20 중요한회로이며, 가산기회로의로직처리시간이전체디지털회로에많은영향을끼친다. 또한, 움직임추정기의대부분이메모리제어와가산기로구성되어있음을비추어보았을경우, 고속의가산기구조를사용하는것은중요한의미를갖게된다. 16 16 현재블록을이전탐색영역에서한번의블록정합을수행할경우사용되는가산기의개수를정리하면표 1과같이나타낼수있다. MED 블록에서 16개의 4 4 SAD를구하기위하여총 240개의가산기가필요함을알수있다. 표 2는 0.8um 표준셀공정을사용하여각가산기종류에따른칩면적, 게이트지연, 평균전력소모량을나타내었다 [13~14]. RCA(Ripple Carry Adder) 에대한결과값을 1 로정규화한다음나머지가산기에대해결과값을산출하였다. 본논문에서는표 2의결과를토대로, SAD를구하기위한 Adder Tree의가산기로상대적으로적은칩면적의증가로고속처리및전력소모량최소화가가능한 CSA 구조를사용하였다. 그림 9는 8비트 CSA 구조를나타내며, 4비트단위의 RCA에서발생하는 Carry 신호를예측하여 Carry 전파에따른시간지연을줄일수있도록하였다. CSA는 4 비트 RCA를구성하는 4개의전가산기에비트단위로데이터를입력하고, 각전가산기의 Carry 신호를모두 And Gate연산을통해 Carry를 Skip해야할지결정한다. 또한, 4비트 RCA가연이어사용되었을경우에는전단의 4비트 RCA의 Cout_1 Carry 신호와의 And (959)
72 다양한블록크기의전역탐색알고리즘을위한효율적인구조를갖는움직임추정기설계황종희외 그림 9. 8비트 Carry Skip Adder 구조 Fig. 9. 8Bit structure for Carry Skip Adder. Gate 연산을통해 4비트이상의 CSA 구조에대한 Carry Skip을결정하게된다. 만약에모든 Carry 신호 (P7 P1, Cin_1, Cout_1) 가 1 이면, Cout_2는 Cin_1이되어 Carry Skip이된다. 따라서표 2에서와같이 CSA 의입력비트수가 8비트에서 16비트로증가하면로직 Delay 시간이 8비트입력보다더많이감소하게된다. 4. 41개의 SAD값계산블록 41개의 SAD값계산 (41 SADs Calculation) 블록은 MED 블록에서생성된 16개의 4 4 SAD 값들을사용하여 8 8, 8 16, 16 8, 16 16의매크로블록모드와 4 4, 4 8, 8 4의서브매크로블록모드에대한 SAD값을계산한다. 4 4 SAD와동일하게 Adder Tree 구조를통해구현이되었으며, 3개의 4비트 RCA를직렬로연결한 CSA 구조를적용하였다. 다단으로구성된 Adder Tree를통해서 1단에서는 12비트가산기 16개를사용하여 4 8, 8 4 SAD값을구하고, 이결과를이용하여 2 단에서는 13비트가산기 4개를사용하여 8 8 SAD값을생성한다. 마찬가지로, 3단에서는 14비트가산기 4개를사용하여 8 16, 16 8 SAD값과 4단에서는 15비트가산기 1개를사용하여 16 16 SAD값을각각구한다. 5. 최소 SAD값계산및움직임벡터생성블록최소값계산기블록은그림 10 (a) 의하단부점선영역 41개가병렬로배열되어있으며, 매클럭마다 7가지의매크로및서브매크로블록에대한새로운 SAD값 41개가각영역으로입력된다. 최소값생성과정은그림 10(a) 와같이입력되는 SAD값을 Register 에저장하고, 동시에이전클럭에최소의 SAD값이저장되어있는 Register 값과비교하여입력되는 SAD값이더작으면 1 비트 MUX에서 1 을출력하여새로운값으로최소의 SAD에대한 Register값을갱신한다. 그렇지않은경우에는 MUX에서 0 을출력하여기존의최소 SAD값이유지된다 [15]. 탐색영역이 (-16,-16) (15,15) 인경우에는 그림 10. (a) 최소 SAD 계산및움직임벡터생성구조, (b) 움직임벡터생성방법 Fig. 10. (a) Minimum SAD calculation and motion vector generation unit's architecture. (b) The generation method of motion vector. 256번의블록정합이요구되므로, 매클럭마다 41개의값이입력되어 256번의최소값계산을수행하게된다. 최소값계산블록에서는그림 8의제안된 AD 구조와같이최소값계산기의비교기에대해선계산기법을이용하여구현함으로써, 입력 Switching Activity를줄일수있도록하였다. 다음은움직임벡터생성방법으로, 그림 10(b) 와같이탐색영역내에서현재블록이이동하는횟수를 Count 함으로써, 움직임벡터를구할수있다. 현재블록이왼쪽윗부분부터이동을하기때문에이부분의 Count가 1이되고, 이동하면서탐색영역의마지막부분에도달했을때에는 Count가 256이된다. 그리고 Count 에해당되는움직임벡터값은 LUT(Look-Up Table) 형태로저장하여 Count값에맞게출력될수있도록하였다. 비교기블록에서매클럭마다입력되는 41개의 SAD 값과기존의 41개의값과비교하여, 더작은값이입력되면기존에저장되어있는움직임벡터값을대신하기위해서 Count값에따라움직임벡터값을저장하고있는 LUT에 Enable 신호를출력하여움직임벡터값을바꾸게된다. Counter 값이 256를가리키면, 다음클럭에 (960)
2009 년 11 월전자공학회논문지제 46 권 SD 편제 11 호 73 Count 및움직임벡터값은초기화된다. 6. I2C 통신을위한인터페이스회로블록일반적으로, I2C(Inter Integrated Circuit) 는주변장치를단지두가닥의신호선 ( 직렬데이터와직렬클럭 ) 으로만연결하여동작하는양방향직렬버스규격을말한다 [16]. 여기서, I2C는움직임추정에대한하드웨어블록을 FPGA 또는 ASIC으로구현한후주요신호를 PC 가 Master가되어제어하기위해사용되었다. 그림 4의 Slave 블록은외부에서풀업저항이연결된직렬데이터 (SDA) 와직렬클럭 (SCL) 이라는두개의양방향오픈컬렉터라인을사용하여, Master 인 PC의명령을 RS-232 단자를통해전달받는다. 이때, PC에서 Register Control 블록에설정된 Register Set의데이터를변경함으로써, SRAM의주소생성범위제어, 탐색영역조절, 탐색영역내에서현재매크로블록의이동방향조절, 움직임벡터의 LUT 생성등의제어가외부사용자에의해가능하도록하였다. 이를통해, 위에서언급된신호를변경하고자할경우에하드웨어를구성하는로직의변경없이결과를바로확인할수있도록하였다. Ⅳ. 실험및고찰본문에서제안된움직임추정기구조는 Verilog HDL (Hardware Description Language) 을이용하여설계하였고, Modelsim 6.0d에의해동작시뮬레이션 (Functional Simulation) 을수행하였다. 그다음, Synplify 합성툴을이용하여게이트레벨구조분석및 Netlist 추출하여타이밍시뮬레이션을통해움직임추 정기구조에대한검증을완료하였다. 시뮬레이션결과는그림 11과같으며, 입력 Sequence 로초당 30 프레임의순차적인 CIF급 foreman 영상데이터를이용하여움직임추정을위한현재프레임과참조프레임의데이터로사용하였다. 현재프레임을부호화할때사용되는참조프레임은연속적으로배열된영상데이터에서현재프레임바로이전프레임이필요로한다. 따라서특정한영상프레임에대한움직임추정이끝날때마다순차적인 2 프레임영상데이터를텍스트파일로변환하여 FPGA에내장된 SRAM의입력데이터로사용하였고, 탐색영역은 (-16, -16) (15, 15) 로설정하였다. 최초 16클럭동안 MED 블록에배열되어있는 16개의 MED_X 에 16 16 현재블록과이전블록에대한데이터가입력된다. 즉, 16개의 SRAM 에서는시스템클럭에맞춰동시에 8비트버스크기로 16 1 픽셀의데이터가출력된다. 따라서처음으로블록정합을시작하기위해서는 16클럭동안은 SRAM 으로부터입력만받게된다. 그다음클럭부터는스캔방향에따라 SRAM 으로부터탐색영역에대한 16 1 또는 1 16 데이터만을입력받아실시간으로움직임추정을수행하게된다. 움직임추정기내부에서데이터흐름을살펴보면, 16클록동안데이터를입력받은 MED블록은참조블록에대한 16개의 4 4 SAD값을계산하여출력하고, 이값을이용하여그다음 17번째클럭에서 7 가지블록크기에해당하는 41개의값을 Adder Tree를통해만들어내게된다. 최소값계산블록과움직임벡터생성부에서는탐색횟수만큼입력되는 41개의값을이전에저장된최소값과비교하여최소값을갱신하게된다. 따라서움직임추정기에서최초로출력하는데걸리는클럭수는 17이되고, 그림 11. 움직임추정기의타이밍시뮬레이션결과 Fig. 11. The timing simulation result of motion estimator. (961)
74 다양한블록크기의전역탐색알고리즘을위한효율적인구조를갖는움직임추정기설계황종희외 전체탐색범위가 (-16, -16) (15, 15) 이므로, 현재블록과 Best Matching 되는참조블록을찾는데필요한총클럭수는 17+(16 16)=273이된다. 설계된구조에대한모듈별 Delay와게이트카운트수를비교하기위하여 FPGA 구현및검증을진행하였다. 사용된 FPGA는 Virtex 4 계열의 XC4VLX200이고, 패키지는 FF1513, Speed 등급은 -11을적용하였다. 일반적인구조와제안된구조의 Delay를정확하게비교하기위해서합성및 P&R(Place & Route) 정보는동일하게유지하였다. 제안된움직임추정기구조에는선계산기법, Carry Skip Adder 구조, I2C 통신을위한인터페이스블록등이적용되었으며, 일반적인구조는참고문헌의논문 [7~8, 11] 에서단위블록의병렬배열을통한고속처리구조를사용하였다. 일반적인구조는선계산방법을이용한입력데이터예측방법대신전체입력비트에대한연산을수행한후절대값및최소값을구하는구조와 Ripple Carry Adder가적용되었다. 또한탐색영역이고정되어사용됨으로 I2C 인터페이스블록이포함되지않았다. 표 3과같이 Delay는로직에서차지하는 Gate Delay와로직의입 출력을연결해주는 Net Delay로구성된다. MED블록에서는선계산과 CSA 구조를적용하였으며, 일반적인구조에비해 19.89% 정도의 Delay 감소효과를얻을수있었다. 여기서, 선계산방법에 RCA 구조를적용하였을경우에는 Total Delay가 13.203ns로제안된구조의 Total Delay 표 3. 움직임추정기의블록별 Delay 비교. Table 3. Delay comparison for blocks of motion estimator. MED Gate Delay Net Delay Total Conventional 7.124 8.478 15.602 Proposed 5.429 7.070 12.499 % reduction 23.79 16.61 19.89 41 SADs Calculation Gate Delay Net Delay Total Conventional 8.635 4.575 13.210 Proposed 6.149 4.159 10.308 % reduction 28.79 9.09 21.97 Minimum SAD Calculation & Motion Vector Generation Gate Delay Net Delay Total Conventional 3.908 0.326 4.234 Proposed 3.774 0.303 4.077 % reduction 3.43 7.06 3.72 보다대략 0.704ns만큼증가하게된다. 따라서 CSA구조에선계산방법을결합하여사용하였을경우에 Delay 감소효과를최대화시킬수있다. 41개의 SAD값계산블록에서는 CSA 구조를적용하여 21.97% 의 Delay 감소와최소 SAD값계산및움직임벡터생성블록에서는선계산기법을적용하여 3.72% 의 Delay 감소를얻을수있었다. 하드웨어의동작주파수에영향을끼치는임계경로는 Delay가가장많은 MED 블록에서나타나며, 일반적인구조가 64MHz (1/15.602) 의동작주파수를갖는반면에제안된구조는 80MHz(1/12.499) 의동작주파수를얻을수있었다. 이를통해초당 30프레임의 CIF 영상을기존구조에비해고속으로처리할수있게되었다. 여기서게이트수를분석하면, 일반적인구조는게이트카운트수가 130.3K이고, 제안된구조는 142.6K로 9.43% 증가하였다. 게이트수증가요인은 I2C 통신을위한인터페이스회로추가와고속의가산기사용으로인해발생하였다. Ⅴ. 결론움직임추정은영상부호화시스템에서큰비중을차지하는부분으로, 실시간으로동작하기위해서는효율적인구조를필요로한다. 본논문에서는많은연산량을효율적으로줄일수있도록병렬처리를바탕으로움직임추정감지블록, 41개의 SAD(Sum of Absolute Difference) 값계산블록, 최소의 SAD값계산과움직임벡터생성블록을제안하였다. 움직임추정감지블록과최소의 SAD값계산기에서는선계산방법을적용하여입력 Switching Activity를줄여고속구현이가능하도록하였으며. 움직임추정감지블록과 41개의 SAD값계산블록에서가장많은부분을차지하는가산기구조를일반적으로사용되는 Ripple Carry Adder 대신에 Carry Skip Adder를적용함으로써, Adder Tree 구조를고속으로처리할수있도록하였다. 또한외부에서탐색영역제어와같은주요변수를쉽게제어할수있도록하여, 하드웨어구조의효율성을높였다. 시뮬레이션및 FPGA 검증결과, 움직임추정기의임계경로를발생시키는 MED블록에서일반적인구조를적용했을때보다 19.89% 의 Delay 감소효과를얻을수있었다. 따라서제안된움직임추정기는고속처리를중요한인자로사용하는시스템의경우에널리사용될수있을것이다. (962)
2009 년 11 월전자공학회논문지제 46 권 SD 편제 11 호 75 참고문헌 [1] Suk-Ju Kang, Dong-Gon Yoo, Sung-Kyu Lee, and Young Hwan Kim, Hardware Implementation of Motion Estimation Using a Sub-sampled Block for Frame Rate Up-Conversion, International SoC Design Conference(ISOCC) 2008, pp. 101-104, Nov. 2008. [2] Chun-Ho Cheung and Lai-Man Po, A Novel Cross-Diamond Search Algorithm for Fast Block Motion Estimation, IEEE Trans. Circuit and Systems for video technology, Vol. 12, no. 12, December 2002. [3] B. M. Wang, J. C. Yen and S. Chang, Zero waiting cycle hierarchical block matching algorithm and its array architectures, IEEE Trans. Circuit and Systems for video technology, Video Technology, Vol. 4, pp. 18-28, Feb. 1994. [4] R. Srinivasan and K. R. Rao, Predictive coding based on efficient motion estimation, IEEE Trans. Commun., Vol. COM-33, pp. 888-896, Aug. 1985. [5] Xiangwen Wang, Jun Sun, Rong Xie, Songyu Yu, and Wenjun Zhang, An improved block size selection method based on macroblock movement characteristic, multimedia tools and applications, Vol. 43, no. 2, pp. 131-143, May 2009. [6] Zhou Z, Sun MT and Hsu YF, Fast variable block-size motion estimation algorithms based on merge and split procedures for H.264/MPEG-4 AVC, ISCAS2004, Vol. 3, pp. 725-728, May 2004. [7] Siou-Shen Lin, Po-Chih Tseng and Liang-Gee Chen, Low-power Parallel Tree Architecture For Full Search Block-Matching Motion Estimation, ISCAS2004, Vol. 2, pp. 313-316, May 2004. [8] Subarna Chatterjee and Amlan Chakrabarti, Parallel Hardware Design for Motion Estimation, ACEEE 2009 Academy Publisher, International Journal of Recent Trends in Engineering, Vol. 1, no. 1, pp. 653-657, May 2009. [9] 윤미선, 장승호, 문동선, 신현철, H.264 동영상압 축에서의가변블록과다중프레임을지원하는효 율적인움직임추정방법, 전자공학회논문지, 제 44권 SD편, 제5호, 58-64쪽, 2007년 5월 [10] Swee Yeow Yap and John V. McCanny, A VLSI Architecture for Advanced Video Coding Motion Estimation, ASAP'03, Proceedings. IEEE International Conference on, pp. 293-301, June 2003. [11] Ching-Yeh Chen et al., Analysis and architecture design of variable block size motion estimation for H.264/AVC, IEEE Trans. Circuit and Systems for video technology, Reg. Paper, Vol. 53, no. 2, pp. 578-593, Feb. 2006. [12] Jen-Chieh Tuan, Tian-Sheuan Chang, and Chein-Wei Jen, On the Data Reuse and Memory Bandwidth Analysis for Full-Search Block-Matching VLSI Architecture, IEEE Trans. Circuit and Systems for video technology, Vol. 12, no. 1, pp. 61-71, January 2002. [13] R. Zimmermann and H. Kaeslin, Cell-Based multilevel Carry-Increment Adders with Minimal AT- and PT-Products, unpublished manuscript, http://www.iis.ee.ethz.ch/~zimmi/ [14] A. Amin, High-Speed Self-Timed Carry-Skip Adder, Institution Engineering Technology- IET, IEE Proceedings - Circuit Devices and Systems, pp. 574-582, Vol. 153, no. 6, December 2006. [15] 장영범, 오세만, 김비철, 유현중, H.264 움직임추 정을위한효율적인 SAD 프로세서, 전자공학회 논문지, 제 44권 SP편, 제2호, 74-81쪽, 2007년 3월 [16] http://www.semiconductor.philips.com/buses/i2c (963)
76 다양한블록크기의전역탐색알고리즘을위한효율적인구조를갖는움직임추정기설계황종희외 저자소개 황종희 ( 정회원 ) 2001 년인하대학교반도체공학과학사졸업. 2005 년인하대학교정보통신공학과석사졸업. 2009 년 ~ 현재연세대학교전기전자공학과박사과정 2001 년 LG 전자평택 DAV 사업부입사 2005 년 ~ 현재 LG Display 선행개발회로설계선임연구원 < 주관심분야 : 영상신호처리, 반도체 SOC> 최윤식 ( 정회원 ) 1979 년연세대학교전기공학과학사졸업 1984 년 Case Western Reserve Univ. 시스템공학과졸업. 1987 년 Pennsylvania State Univ. 전기공학과석사졸업 1990 년 Purdue Univ. 전기공학부박사졸업 1990 년 ~1993 년 ( 주 ) 현대전자산업전자연구소책임연구원 1993 년 ~ 현재연세대학교전기전자공학부정교수 < 주관심분야 : 비디오, 영상신호처리, HDTV> (964)