Microsoft Word doc

Transcription

1

2 工學碩士學位請求論文 모바일프로젝션디스플레이를위한프레임레이트변환방법 An efficient frame rate conversion method for mobile projection displays 2007 年 8 月 仁荷大學校情報通信大學院情報通信工學科李鍾玉

3 工學碩士學位請求論文 모바일프로젝션디스플레이를위한프레임레이트변환방법 An efficient frame rate conversion method for mobile projection displays 2007 年 8 月 指導敎授金椿宇 이論文을碩士學位論文으로提出함 仁荷大學校情報通信大學院情報通信工學科李鍾玉

4 이論文을李鍾玉의碩士學位論文으로提出함 2007 年 8 月 主審 副審 委員

5 요약 요약 최근, 휴대폰은멀티미디어로의복합화되고있으며단순히전화를걸고받는기능뿐만아니라사진촬영, 웹탐색, 게임등과같은새로운기능을포함하고있다. 특히 T-DMB(Terrestrial digital multimedia broadcasting) 지원휴대폰의수요가급격히확대되고있다. 또한빔프로젝션 (beam projection) 기능을갖춘휴대폰인휴대폰프로젝션디스플레이 (Mobile projection display) 가주목받고있다. 휴대폰프로젝션디스플레이와같은영상출력장치의성능을결정하는요인으로는가격, 크기, 디자인, 수명, 소모전력및화질등을들수있다. 이와같은요소들중에서화질은다른상품들과차별화할수있는주요한요인들중의하나이다. 휴대폰프로젝션디스플레이의입력인 T-DMB의프레임레이트는초당 30 프레임이다. 이와같이 T-DMB의낮은프레임레이트때문에휴대폰프로젝션디스플레이상에서 T-DMB를보는경우, 모션져더 (Motion judder) 나블러 (blur) 아티팩트 (artifact) 와같은문제점들이발생한다. 이와같은문제점을해결하고 T-DMB의화질을향상시키기위하여본논문에서는프레임레이트변환기술이사용되었다. 본논문에서제안하는프레임레이트변환기술은휴대폰을대상으로하기때문에하드웨어복잡도는최소화되어야한다. 프레임레이트변환기술은비디오코딩, 비디오포맷변환, LCD 상의모션블러저감기술등을위하여널리개발되고있다. 프레임반복이나평균과같은간단한프레임레이트변환기술은움직이는대상에모션져더나블러와같은 i

6 요약 문제점을발생시킨다. 이와같은아티팩트를제거하기위하여움직임보상프레임레이트변환기술이개발되고있다. 움직임보상프레임레이트변환기술은크게움직임예측기술과보간기술로구분된다. 예측된움직임정보의정확성과처리속도는움직임예측기술의성능을결정하는중요한요소들이다. 예측된움직임벡터의정확성을향상시키기위한기존의프레임레이트변환기술은많은계산량과복잡한하드웨어를필요로하기때문에휴대폰의실시간처리에적합하지않다. 본논문에서는휴대폰프로젝션디스플레이상에서디스플레이되는 T-DMB의화질을향상시키기위하여효과적인프레임레이트변환기술을제안한다. 블록의크기는움직임예측기술의성능을결정하는중요한요소이다. 움직임이적은영역에서는비교적큰블록의크기가적합한반면, 움직임이많은영역에서는비교적작은블록을사용하는것이적합하다. 제안하는움직임예측방법에서는움직이는대상의움직임활동도 (motion activity level) 에따라다양한크기의블록과탐색영역을사용한다. 다양한크기의블록을사용하는기존의움직임예측방법에는블록의크기를결정하는데많은계산량을필요로하기때문에실행시간이많이소요된다. 반면, 제안하는방법에서는블록의크기를결정하는데필요한계산량이적기때문에휴대폰을대상으로적용하기적합하다. 본논문에서는움직임벡터의정확성을향상시키기위하여정지움직임검출 (zero motion detection) 기술이사용되었다. 실험을수행한결과, 제안하는방법은기존의방법에비하여필요한하드웨어복잡도는낮은반면, 결과영상의화질은향상되었다. ii

7 요약 Abstract In the recent years, mobile phones have taken on many new functions such as photography, web access, gaming beyond just making calls. Specially, the terrestrial digital multimedia broadcasting (T-DMB) capable mobile phone is becoming popular. The mobile phone with beam projection capability, called as mobile projection display, is beginning to make a mark. The mobile projection display is designed to provide convenience by displaying the T-DMB on the projected wider screen for consumers. Visual quality and computational complexity are major factors which determine performance of video communication on mobile applications. However, there are problems with watching the T-DMB on mobile projection display due to its low frame rate. These include motion jerkiness, judder, and blurring on moving object with constant velocity. In order to improve motion image quality on mobile projection displays, frame rate conversion (FRC) algorithms is employed in this thesis. FRC algorithms have been widely studied for coding of video sequences and/or converting video format. For FRC algorithm applied to mobile applications, computational complexity and size of memory resources are important limiting factors. However, most of the frame rate conversion algorithms for high visual quality demand the heavy computational burden and consequent huge hardware cost. In this paper, we propose a FRC method to improve the visual quality for mobile projection displays. The block size is primary factor which determine performance of motion estimation. In stationary area, larger block size is suitable to find the motion vector. iii

8 요약 On the other hand, in the motion regions, relatively small block size is desirable. In the proposed motion estimation algorithm, the adaptive block size and search window are utilized depending on the motion activity level of block. The motion activity level for 8x8 size block is calculated based on the summed absolute difference (SAD). The type of 8x8 size block is determined whether it is motion type or no-motion type according to motion activity level of block. The neighboring blocks with no-motion type are merged into a larger block. When the current block is no-motion type, the small search window size is used to reduce the computational complexity. In order to improve the accuracy of estimated motion vectors, the zero motion detection technique is employed. The proposed method achieves better visual quality performance with low complexity to be utilized for mobile projection displays. iv

9 목차 목차 1. 서론 연구배경 프레임레이트변환기술의분류 움직임정보를사용하지않는방법 프레임반복 (Frame repetition) 프레임평균 (Frame averaging) 움직임정보를사용하는방법 (Motion compensated frame rate conversion) 본논문의구성 기존의움직임예측 (Motion estimation) 방법 블록정합알고리즘 COST 함수 [1] 탐색방법 Full search Sub-sampled full search [2] Alternating 4:1 화소서브샘플링 (pixel sub-sampling) Sub-sampled motion field estimation Sub-block motion field estimation v

10 목차 Three step search [3] New three step search [4] D logarithm search [5] Block-based gradient descent search [6] Diamond search [7] 움직임벡터 (Motion vectors) 의결정방법 계층적 (Hierarchical) 움직임예측 [8] 가변크기의블록을이용한움직임예측 [9] 움직임벡터의후처리 (post-processing) [1] 기존의프레임보간 (Frame interpolation) 방법 [11] Temporal weighted averaging Motion compensation average Static median filtering Dynamic median filtering Soft switching Cascaded median filters 제안하는움직임예측방법 각블록에대한움직임활동도의예측단계 블록과탐색윈도우크기의결정단계 움직임벡터의예측단계 제안하는프레임보간방법 vi

11 목차 6. 실험결과 결론 참고문헌 vii

12 목차 표목차 표 2-1. TSS와 NTSS의비교 표 2-2. 탐색윈도우의중심주변에움직임벡터가존재할확률 표 2-3. 기존의탐색방법에대한화소당평균 MSE 표 2-4. 움직임벡터를예측하는데필요한평균탐색점의개수 표 2-5. 생성된프레임영상의평균 PSNR 표 4-1. 블록타입에따라사용되는탐색윈도우의크기 표 6-1. 기존블록정합알고리즘의계산량비교 표 6-2. 제안하는방법과 full search의계산량비교 표 6-3. 제안하는방법과 full search의계산량비교 표 6-4. 탐색윈도우의중심으로부터떨어진거리안에움직임벡터가존재할확률 [7] viii

13 목차 그림목차 그림 1-1. 프레임레이트변환기술... 4 그림 1-2. 프레임레이트변환기술의분류... 5 그림 1-3. 프레임반복 [1]... 6 그림 1-4. 프레임평균 [1]... 7 그림 1-5. Motion compensated interpolation[1]... 9 그림 2-1. 블록정합알고리즘 [1] 그림 x8 블록의 alternating 서브샘플링패턴 그림 2-3. 탐색영역상에서 4개의서브샘플링패턴의사용순서 그림 2-4. Alternating 순서에의해사용되는픽셀 그림 2-5. 임의의 alternating 순서 그림 2-6. 움직임필드에사용된서브샘플링패턴 그림 2-7. 움직임필드에사용된서브블록 그림 2-9. 탐색영역내에존재하는 local minima 그림 탐색영역내의 MV 분포 ( 블록크기 : 16x16) 그림 NTSS의알고리즘의예 그림 LOGS 알고리즘의예 그림 BBGDS 알고리즘의예 그림 두가지형태의탐색패턴 ix

14 목차 그림 DS 알고리즘의예 그림 단계피라미드영상의예 그림 가변크기의블록을이용한움직임예측방법의블록다이어그램. 40 그림 벡터메디안필터링 [3x3] 의예 그림 벡터메디안필터링의효과 그림 두움직임벡터사이의거리 그림 각방법에의하여생성된프레임의예 그림 가변크기의블록을이용한방법에의해생성된프레임영상 그림 움직임벡터의후처리과정에사용된움직임벡터 그림 3-1. Temporal weighted averaging 방법을적용한결과영상 그림 3-2. Motion compensation average 방법을적용한결과영상 그림 3-3. Motion compensation average 방법에의한정지텍스트에서의 artifact 그림 3-4. Static median filtering 방법을적용한결과영상 그림 3-5. Static median filtering 방법에의한정지텍스트에서의화질향상 그림 3-6. Dynamic median filtering 방법을적용한결과영상 그림 3-7. Dynamic median filtering 방법에의한정지텍스트에서의화질향상 그림 3-8. 실험시퀀스의한프레임 그림 3-9. 실험프레임상에선택된신호의분포 그림 4-1. 제안하는프레임레이트변환방법의전체흐름도 그림 4-2. 제안하는움직임예측방법의순서도 그림 4-3. 블록타입을결정하는방법의순서도 x

15 목차 그림 4-5. 보간된영상에적용된블록크기의표현 그림 4-6. 제안하는움직임벡터의예측단계 그림 4-7. Forward 움직임예측에효과적인자막부분의예 그림 5-1. 제안하는프레임보간방법의순서도 그림 6-1. 기존의고속블록정합알고리즘과제안하는방법의성능비교 그림 6-2. 기존의가변크기의블록을이용한움직임예측방법과제안하는방법의성능비교 그림 6-3. 기존의방법과제안하는방법의화질평가 (Foreman) 그림 6-4. 기존의방법과제안하는방법의화질평가 (Football) 그림 6-5. 기존의방법과제안하는방법의화질평가 (Flower garden) xi

16 1. 서론 1.1 연구배경 디지털영상을표현하는장치는영상을표현하는방식에따라휴대폰프로젝션디스플레이, CRT, LCD, PDP와같은디스플레이장치와프린터, 팩스와같이염료를사용하는하드카피 (hard copy) 출력장치로구분된다. 최근, 휴대폰은멀티미디어로의복합화되고있으며단순히전화를걸고받는기능뿐만아니라사진촬영, 웹탐색, 게임등과같은새로운기능을포함하고있다. 특히 T- DMB(Terrestrial digital multimedia broadcasting) 지원휴대폰의수요가급격히확대되고있다. 또한빔프로젝션 (beam projection) 기능을추가적으로갖춘휴대폰인휴대폰프로젝션디스플레이 (Mobile projection display) 가주목받고있다. 휴대폰프로젝션디스플레이는투사된더넓은화면상에서 T-DMB를보여줌으로써사용자의편의를증대시키고자개발되고있다. 휴대폰프로젝션디스플레이와같은영상출력장치의성능을결정하는요인으로는가격, 크기, 디자인, 수명, 소모전력및화질등을들수있다. 이와같은요소들중에서화질은다른상품들과차별화할수있는주요한요인들중의하나이다. 휴대폰프로젝션디스플레이의입력인 T-DMB의프레임레이트는초당 30 프레임이고, 프레임의크기는 QVGA(320x240) 이다. 이와같은 T-DMB의낮은프레임레이트때문에휴대폰프로젝션디스플레이상에서 T-DMB를보는 1

17 데에여러가지문제점들이발생한다. 특히, 일정한속도로이동하는자막부분에서모션져더 (Motion judder) 나블러 (blur) 아티팩트 (artifact) 가발생한다. 이와같은문제점을해결하고 T-DMB의화질을향상시키기위하여본논문에서는프레임레이트변환기술이사용되었다. 본논문에서제안하는프레임레이트변환기술은휴대폰을대상으로하기때문에하드웨어복잡도는최소화되어야한다. 프레임레이트변환기술은비디오코딩, 비디오포맷변환, 디스플레이분야에서다양하게사용되고있다. 프레임레이트변환기술이란낮은프레임레이트의입력동영상을높은프레임레이트의출력동영상으로변환시, 특정아티팩트없이입력동영상의프레임수를증가시키는기술을의미한다. 이아트팩트에는모션져더, 모션블러, 블록아티팩트등이포함된다. 모션져더나움직임에서의 jerkiness 현상은대상의움직임이부드럽지않고부자연스럽게연결되어보이는현상이다. 이것은카메라패닝이나일정한속도로이동하는대상에서관찰될수있다. 모션블러는움직이는물체의경계부분이선명하게보이지않고잔상효과와같이흐릿하게보이는현상이다. 모션블러는느린응답속도를갖는 LCD 상에서동영상이재생될때발생되는문제점중에하나이다. 그림 1-1은프레임레이트변환기술을적용함으로써낮은프레임레이트의입력동영상을높은프레임레이트의출력동영상으로변환하는일례를나타낸것이다. 그림 1-1에서옅은회색의사각형은초당 30프레임의프레임레이트를갖는입력동영상의프레임들을나타내고, 짙은회색의사각형은입력프레임들을이용해서프레임레이트변환기술에의하여생성된 2

18 프레임을나타낸다. 프레임레이트변환기술은크게움직임정보를사용하는지의여부에따라서크게두가지범주로나눌수있다. 움직임정보를사용하지않는방법에는프레임반복 (Frame repetition) 과프레임평균 (Frame averaging) 기술이포함된다. 이기술에의한출력동영상에서는모션져더나블러와같은아티팩트가발생될수있다. 움직임정보를사용하는방법은움직임보상프레임변환기술 (Motion compensated frame rate conversion: MC- FRC) 이있다. MC-FRC 기술은움직임예측기술과프레임보간기술로구분될수있다. 움직임예측기술에는블록정합알고리즘 (Block matching algorithm: BMA) 이널리사용된다. BMA은 MPEG(Moving Picture Experts Group) 이나 H. * 시리즈에서도사용되고있다. 움직임예측이정확하게수행되지않는경우, MC-FRC에의한결과동영상에는블록아티팩트가발생한다. 동영상에서의블록아티팩트는모션블러보다사람눈에더거슬리기때문에블록아티팩트를감소시키기위한여러가지 MC-FRC 기술이개발되고있다. 그러나이와같이움직임정보의정확성을향상시키기위한 MC-FRC 기술은많은계산량을필요로하기때문에휴대폰에서의실시간처리에적합하지않다. 본논문에서는휴대폰프로젝션프로젝션상에서 T-DMB의화질을향상시키기위하여효과적인프레임레이트변환기술이제안된다. 또한제안하는프레임레이트변환기술이휴대폰프로젝션디스플레이의실시간 처리에사용되기위하여필요한계산적 복잡도와하드웨어메모리량을 최소화하였다. 3

19 30 fps 60 fps Original frames Interpolated frames 그림 1-1. 프레임레이트변환기술 1.2 프레임레이트변환기술의분류 지금까지제안되어온프레임레이트변환방법들은그림 1-2와같이대상의움직임정보를사용하는지의여부에따라크게두가지범주로나눌수있다. 대상의움직임정보를사용하지않는방법에는프레임반복과프레임평균이있고, 움직임정보를사용하는방법에는 MC-FRC 기술이있다. MC-FRC 기술은대상의움직임정보를예측하는움직임예측 (motion estimation: ME) 단계와예측된움직임정보를이용해서새로운프레임을생성하는프레임보간 (motion compensated interpolation: MCI) 단계로구분된다. 움직임예측단계는처리속도를향상시키는움직임예측방법과예측된움직임정보의정확성을향상시키는움직임예측방법으로구분된다. 본절에서는기존의프레임레이트 4

20 변환방법에대하여자세히설명한다. 움직임정보 사용안함 프레임레이트 변환기술 움직임정보 사용함 ME Fast ME Accurate ME MC-FRC MCI 그림 1-2. 프레임레이트변환기술의분류 움직임정보를사용하지않는방법 이범주에는프레임반복 (Frame repetition) 과프레임평균 (Frame averaging) 방법이포함된다. 이와같은방법들은대상의움직임을예측하지않고새로운프레임을생성하기때문에계산량이적고하드웨어구현이용이하다. 이방법은움직임이거의없는배경영역에서는좋은결과를보인다. 하지만움직임이있는영역에서는모션 jerkiness나모션블러와같은문제점이발생한다 프레임반복 (Frame repetition) 프레임반복기술은이전프레임을반복함으로써새로운프레임을 5

21 생성시키는간단한방법이다. 그림 1-3은프레임반복에의하여생성된움직이는대상의위치를나타낸다. 가로축은프레임순서를나타내고, 세로축은일정한속도로이동하는대상 (object) 의위치를나타낸다. 그림 1-3에서대각선은대상의경로를나타낸다. 프레임반복에의하여생성된프레임상의대상의위치는대상의경로상의위치와는다를것이다. 그림 1-3의 4번째프레임위치에관찰자로부터예상된대상의위치가표시되어있다. 프레임반복방법은움직임이없는영역에서는좋은성능을보이지만움직임이있는영역에서는모션져더와같은문제점을갖는다. 이것은영상화질에대한큰열화를발생시킨다. Position Time Object in original frames Object in interpolated frames Expected position of object in frame 4 그림 1-3. 프레임반복 [1] 6

22 프레임평균 (Frame averaging) 프레임평균기술은보간된출력프레임을얻기위하여두개의이웃하는프레임들을평균하는방법이다. 이방법은프레임반복방법과마찬가지로움직임이없는영역에서는좋은성능을보이지만, 움직임이있는영역에서는프레임반복방법에의한결과보다심각한모션블러가발생한다. 그림 1-4는프레임평균방법에의하여생성된움직이는대상의위치를나타낸다. 그림 1-4에서대각실선은이동하는대상의움직임경로를나타내고, 대각점선은이전프레임과다음프레임에위치하는대상의이전과다음움직임경로를나타낸다. 대각점선상에위치한두대상의평균에의하여새로운프레임이생성된다. Position Time Object in original frames Object in interpolated frames Expected position of object in frame 4 그림 1-4. 프레임평균 [1] 7

23 1.2.2 움직임정보를사용하는방법 (Motion compensated frame rate conversion) 만약대상의속도를안다면속도에대응되는움직임벡터 (motion vector) 에 의하여입력프레임의픽셀 (pixel) 을이동시키고정확한위치상에대상을 위치시킬수있다. MC-FRC 기술은움직임벡터를예측하는단계와예측된 움직임벡터를이용하여프레임을보간하는단계로구성된다. 또한움직임예측단계의성능은예측된움직임정보의정확도와실행속도에의하여결정된다. 그림 1-5는이웃하는프레임들의 MC 평균에의하여보간된출력프레임을나타낸다. 그림 1-5에서화살표는예측된움직임벡터를나타낸다. 만약움직임벡터가정확하게예측된다면움직임이있는영역에서모션블러현상은발생하지않는다. 하지만움직임벡터를정확하게예측하는것은상당히어렵다. 만약예측된움직임벡터가부정확하다면움직이는영역에서블록아티팩트 (block artifact) 등의문제점이발생된다. 이와같은블록아티팩트는모션블러보다인간시각에더거슬리는아티팩트이다. 또한예측된움직임벡터에대한정확성의정도는대상에따라다르기때문에프레임반복이나평균에의해발생하는모션블러보다더심한화질열화가발생될수있다. 8

24 Original frames Interpolated frames (MC average) Shift over motion vector t-t t t+t t+2t 30fps input frames 60fps output frames 그림 1-5. Motion compensated interpolation[1] 1.3 본논문의구성 본논문의연구대상은프레임레이트변환기술중에서움직임정보를사용하는방법인 MC-FRC를대상으로한다. MC-FRC는위에서언급한바와같이움직임벡터를예측하는움직임예측단계와예측된움직임정보를이용해서새로운프레임을생성하는프레임보간단계로구성된다. 움직임예측을하는방법에는블록정합알고리즘 (Block matching algorithm: BMA) 이널리사용되고있 9

25 다. 블록정합알고리즘은데이터흐름의규칙성, 하드웨어구현의용이성에의하여 MPEG(Moving Picture Experts Group) 비디오코딩에서사용되고있다. 본논문의 2장에서는움직임예측방법인블록정합알고리즘에대하여설명하고, 3장에서는기존의프레임보간방법을설명한다. 4장에서는제안하는프레임레이트변환기술을설명하고, 5장에서는제안하는프레임레이트변환기술의성능을평가하기위한실험방법및결과를제시한다. 10

26 2. 기존의움직임예측 (Motion estimation) 방법 프레임레이트변환방법중에서 MC-FRC 기술은움직이는영역에서비교적좋은성능을나타낸다. MC-FRC 기술은크게대상의움직임벡터를예측하는단계와예측된움직임벡터에의해프레임을보간하는단계로구성된다. 본장에서는기존의움직임예측방법에대하여설명한다. 2.1 블록정합알고리즘 현재, 대부분의비디오코딩에서는데이터흐름의규칙성, 계산의복잡도, 하드웨어구현을고려하여블록정합알고리즘이널리사용되고있다. 블록정합알고리즘은블록단위로탐색영역 (search area) 내에서최소의정합오차를갖는블록을찾고이블록의가로, 세로변위를추정하는알고리즘이다. 블록정합알고리즘에서는영상의한프레임을여러개의블록으로나누고이들의각블록에대하여탐색영역내에서정합오차가가장작은블록을찾는다. 이때처리하고자하는블록과탐색영역내에서가장정합이잘되는블록간의변위를움직임벡터라고한다. 그림 2-1은이전프레임의탐색영역 SA 내에서 X*Y크기의블록에대한움직임벡터를예측하는과정을나타낸다. 그림 2-1에서현재프레임상에있는빗금친블록은현재처리하고자하는블록이고, 화살표는예측된움직임벡터를나타낸다. 11

27 y-2y y-y y y+y y+2y SA t-t x-2x x x+2x Time t x-2x x x+2x 그림 2-1. 블록정합알고리즘 [1] 2.2 COST 함수 [1] 정합오차를계산하기위하여사용되는 COST 함수중에서널리사용되는 것에는 summed absolute difference (SAD), summed square error (SSE), 그리고 normalize cross correlation function (NCCF) 이있다. SAD 는식 2-1 에의하여 계산된다. 여기서 C 는후보움직임벡터의좌표값이고, x 는픽셀의좌표 값을나타낸다. X 는현재처리하고자하는블록의중심좌표값을 나타내고, B(X ) 는 X 를중심으로하는블록을나타낸다. 그리고 t 는시간을 나타내는변수이고, n 과 T 는자연수이다. SSE 와 NCCF 는각각식 2-2 와 2-3 에 12

28 13 의하여계산된다. ( ) ( ) ( ) = ) (,,,, X B x T n t C x F t x F t X C SAD (2-1) ( ) ( ) ( ) [ ] = ) ( 2,,,, X B x T n t C x F t x F t X C SSE (2-2) ( ) ( ) ( ) ( ) ( ) 2 1 ) ( ) ( 2 2 ) (, ), ( ), ( ), (,, = X B x X B x X B x T n t C x F t x F T n t C x F t x F t X C NCCF (2-3) SAD 는구현하기에가장간단하다. SSE 계산에필요한하드웨어복잡도는 SAD 의경우보다더높다. SSE 는제곱연산을하기때문에오차값의범위를표현하는데더많은비트수가필요하다. SSE 는 SAD 보다약간더좋은결과를보이지만이것이하드웨어결점을능가하지는않는다. 따라서실시간처리에 SAD 가널리사용된다. NCCF 는곱셈과나눗셈을필요로하기때문에복잡한하드웨어가필요하다. 하지만 cross correlation 이시간영역이아닌주파수영역에서계산되는경우, fast Fourier transform (FFT) 의 VLSI 구현이비디오데이터레이트상에서가능해지고있다. NCCF 는사진에서의밝기변화나 contrast 변화에잘대응할수있다.

29 2.3 탐색방법 탐색영역내에서현재처리하고자하는블록과의최소정합오차를갖는블록을찾기위하여사용되는여러가지탐색 (search) 방법들이개발되고있다. Full search는탐색영역내의모든위치에대하여탐색을수행하는가장간단한블록정합알고리즘이다. Full search의계산량을감소시키고실행속도를향상시키기위하여여러가지고속블록정합알고리즘이개발되고있다. 본절에서는여러가지탐색방법들에대하여자세히설명한다 Full search Full search는가장간단한블록정합방법이다. Full search에서는탐색범위내의가능한모든후보움직임벡터에대하여정합오차를계산한후에움직임벡터를예측한다. 이방법은모든후보움직임벡터에대하여정합오차를계산하기때문에계산량이많다. 따라서 Full search는실시간비디오코딩응용분야및소프트웨어구현에사용되기어렵다. 이와같은문제점을해결하기위하여여러가지고속블록정합방법 (Fast block matching algorithm) 들이개발되고있다. 고속블록정합방법에는탐색영역내의탐색위치를제한하는방법과정합오차계산에사용되는픽셀의수를제한하는방법등이있다. 14

30 2.3.2 Sub-sampled full search [2] 이범주에속하는기법들은정합오차의계산에사용되는픽셀의수를줄임으로써계산량을감소시킨다. 대표적인방법으로는 alternating 4:1 픽셀서브샘플링 (pixel sub-sampling), sub-sampled motion field estimation, sub-block motion field estimation이있다 Alternating 4:1 화소서브샘플링 (pixel sub-sampling) 그림 2-2는각픽셀에 a, b, c, d 로표시된 8x8 블록을나타낸다. 패턴 A는 8x8 블록내의모든 a 픽셀들로구성된서브샘플링 (sub-sampling) 패턴이다. 마찬가지로패턴 B, C, D는모든 b, c, d 픽셀들로구성된서브샘플링패턴이다. 기존의 4:1 서브샘플링방법에서는패턴 A의픽셀들만블록정합에사용되고그결과계산량은 1/4로감소된다. 그러나 8x8 블록에서 3/4의픽셀들은정합계산에사용되지않기때문에예측된움직임벡터의정확성을신뢰하기어렵다. 이와같은문제점을보완하기위해제안된 Alternating 4:1 화소서브샘플링기법에서는네개의서브샘플링패턴 A, B, C, D를모두사용한다. 15

31 그림 x8 블록의 alternating 서브샘플링패턴 그림 2-3은이전프레임에서탐색영역의일부픽셀들을나타낸것이다. 각픽셀은 1, 2, 3, 4 로표시되어있다. 후보블록의첫번째픽셀 ( 블록의 upperleft 위치 ) 이 1인경우정합오차계산에는패턴 A의픽셀들만사용된다. 그림 2-3(a) 의경우패턴 A에대한정합오차를계산한후에한픽셀오른쪽에위치한후보블록에대한정합오차를계산할때에는패턴 D만사용된다. (a) alternating 순서 1 (b) alternating 순서 2 그림 2-3. 탐색영역상에서 4 개의서브샘플링패턴의사용순서 16

32 처리하고자하는블록마다각패턴 A, B, C, D에대한최소정합오차를갖는 4개의후보블록이선택될것이다. 모든픽셀들을사용해서처리하고자하는블록과 4개의후보블록과의정합오차를구한다음그중에서최소정합오차를갖는블록의위치가최종적인움직임벡터의좌표로선택된다. 4개의서브샘플링패턴의사용순서에의해처리하게되면이전프레임의탐색영역내의모든픽셀들을이용하게된다. 가능한 alternating 순서는모두 6개지만탐색영역내의모든픽셀들을이용하기위해서그림 2-3과같이 2개의 alternating 순서만이사용가능하다. 그림 2-4는그림 2-3(a), (b) 에나타낸순서에의해탐색영역내에서정합오차에계산되는픽셀들 ( 1:, 2:, 3:, 4: ) 을각각나타낸것이다. 이때, 탐색영역은 15x15이고블록의크기는 8x8로가정한다. (a) 순서 1 에의해사용되는픽셀 (a) 순서 2 에의해사용되는픽셀 그림 2-4. Alternating 순서에의해사용되는픽셀 17

33 그림 2-5(a) 는다른 alternating 순서를나타내고, 그림 2-5(b) 는그림 2-5(a) 의 alternating 순서에의해탐색영역내에서정합오차에계산되는픽셀들을나타낸것이다. 검은색블록은후보블록마다사용되는픽셀이중복되는경우를나타낸다. 따라서그림 2-3에나타낸 2개의 alternating 순서만이사용가능하다. (a) 임의의 alternating 순서 (b) 임의의 alternating 순서에의해 사용되는픽셀 그림 2-5. 임의의 alternating 순서 Sub-sampled motion field estimation 비디오시퀀스의움직임필드 (motion field) 는대부분부드럽고천천히변한다. 따라서이웃하는블록들의움직임벡터는거의유사하다. Sub-sampled motion field 방법에서는이와같은특성을이용한다. 처리하고자하는블록과이웃하는 18

34 블록들에대한움직임벡터가서로유사하다는가정하에먼저현재프레임에있는블록의반에대한움직임벡터를예측한다. 그림 2-6은현재프레임상의블록을나타낸것이다. 그림 2-6에서가운데블록 A와인접한어두운블록에대한 4개의움직임벡터를찾고, 이중에서블록 A와최소정합오차를갖는움직임벡터가블록 A의움직임벡터로선택된다. 그림 2-6. 움직임필드에사용된서브샘플링패턴 만약블록 A의움직임이이웃하는블록의움직임의방향및크기와거의같다면이방법은성공적으로움직임벡터를예측할것이다. 만약블록 A가다른방향으로움직이는두개의대상의에지 (edge) 와겹친다면 Sub-sampled motion field 방법에의해예측된블록 A의움직임은두대상들중의하나의움직임과유사할것이며, 이것은 Full search의결과와크게다르지않을것이다. 그러나만약이웃하는블록마다다른방향으로움직이는대상이존재한다면 sub-sampled motion field estimation 방법으로는움직임벡터를정확히예측하기어렵다. 19

35 Sub-block motion field estimation 블록정합방법은블록전체가 하나의움직임을갖는다는가정하에 수행된다. 같은블록안에다른방향이나다른속도로이동하는두개이상의 objects가존재하는경우, 예측된움직임벡터는하나의 object의움직임을나타내거나새로운움직임을나타낼것이다. 따라서만약더작은크기의블록을이용한다면같은블록안에다른방향이나속도로움직이는 object를포함하는경우는줄어들것이다. Sub-block motion field estimation은이와같은특성을이용한다. 블록정합방법에서사용되는블록의크기가 NxN이라고한다면 sub-block motion field estimation에서는 N/2x N/2 크기의블록을사용한다. 그림 2-7은현재프레임에서각블록이 N/2x N/2 크기를갖는 4개의서브블록들 (sub-blocks) 로나눠진것을나타낸다. 그림 2-7에서 A, a, b, c는한블록내의서브블록을나타내고 B, C, D는이웃하는블록의서브블록을의미한다. 그림 2-7. 움직임필드에사용된서브블록 20

36 우선각블록에서왼쪽위에존재하는서브블록 (A, B, C, D) 의움직임벡터를예측한다. 그런다음예측된이웃하는서브블록의움직임벡터를이용해서나머지서브블록의움직임벡터도예측한다. 예를들어그림 2-7에서서브블록 a의움직임벡터는 A와 B의움직임벡터중에서더잘정합되는것으로할당된다. 또한서브블록 b는 A와 C의움직임벡터중에서선택되고, 서브블록 c는 A, B, C, D의움직임벡터중에서선택된다. 그러나 sub-block motion field estimation 방법은더작은크기의블록을사용하기때문에부드러운영역에서움직임벡터를잘못예측할가능성이있다. 이범주에속하는기법들은일정한규칙에의해제한된픽셀들만정합오차계산에사용되기때문에하드웨어적으로사용되는메모리의양이줄어든다 Three step search [3] TSS(Three step search) 는넓은영역에걸쳐몇개의탐색점을조사한후점차범위를좁혀나가는방식으로간단함 (simplicity) 과효율성 (effectiveness) 때문에비디오압축에널리사용된다. 탐색윈도우 (search window) 가 7일때, TSS 알고리즘의첫번째단계에서는 9x9 격자 (grid) 상에균등하게할당된 9개의탐색점을이용해서최소정합오차를갖는점을찾는다. 다음단계에서는이전단계에서찾은최소정합오차의탐색점을중심으로 8개의탐색점을추가한다. 이때두탐색점사이의거리는이전단계의것보다반이다. TSS 알고리즘을수행하는자세한과정은다음과같다. 21

37 Step 1) 그림 2-8(a) 와같이 7x7 grid 상에균등하게위치한 9개탐색점의블록정합오차를구한다. 9개의탐색점중에서최소정합오차의점 ( 그림 2-8(a): ) 을찾는다. Step 2) 그림 2-8(b) 와같이이전단계에서구한최소정합오차의점을중심으로균등하게 8개의탐색점이추가된다. 이때, 탐색점사이의거리가이전단계에비해반으로감소된다. 8개의탐색점에대한정합오차를구하고나서최소정합오차의점 ( 그림 2-8(c): ) 을찾는다. Step 3) 그림 2-8(c) 와같이 Step 2의과정을반복한다. 단, 현단계의탐색점사이의거리는 Step 2에비해반으로감소된다. 9개의탐색점들중에서최소정합오차를갖는탐색점의위치는움직임벡터를의미한다. (a) Step 1 (b) Step 2 (c) Step 3 그림 2-8. TSS 알고리즘의예 탐색영역내의정합오차는 SAD 에의하여구할수있다. 그림 2-9 는탐색 영역내의정합오차를나타낸오차표면 (error surface) 이다. 그림 2-9 를보면 22

38 search 영역내에여러개의 local minima가존재한다는것을알수있다. TSS의첫번째단계에서는탐색영역내에서균등하게할당된탐색점을사용하기때문에 local minimum에빠지기쉽다. 따라서작은움직임을추정할때 TSS 알고리즘은비효율적이다. 그림 2-9를보면정합오차는 global minimum으로부터멀어질수록단조증가하지않는다는것을알수있다. 그러나 global minimum과가까운주변영역 (small neighborhood around the global minimum) 에서는오차표면이단조증가한다. 그림 2-8. 탐색영역내에존재하는 local minima 23

39 2.3.4 New three step search [4] 실제영상시퀀스의블록움직임영역은대부분부드럽고변화가적다. 그결과 global minimum 분포는중심에집중 (center-biased) 되어있다. 그예가그림 2-10에나와있다. 그림 2-10은각영상시퀀스의 100개프레임에전역탐색을수행해서얻은움직임벡터의분포를나타낸다. Salesman 시퀀스의경우, 거의 80% 의블록들이거의정지한것으로간주될수있고대부분의움직임벡터들이중심의 5x5 영역에집중되어있다. Miss America 시퀀스의경우, 움직임벡터의분포가 Salesman보다더분산되어있지만여전히대부분의움직임벡터들은중심에집중되어있다. (a) Salesman sequence (b) Miss American sequence 그림 2-9. 탐색영역내의 MV 분포 ( 블록크기 : 16x16) NTSS 알고리즘은위에서언급한움직임벡터의분포특성을반영한다. NTSS 알고리즘이기존의 TSS 알고리즘과차이점은아래와같다. 24

40 1 첫번째단계에서 TSS에사용된 9개의탐색점들이외에탐색영역의중심영역에 8개의점을추가한다. 2 실행속도를높이기위해거의정지된블록에대해서 halfway-stop 기법이사용된다. 탐색영역이 7x7일때, NTSS의첫번째단계는그림 2-11(a) 와같이 17개의점을탐색한다. 만약첫번째단계에서의최소정합오차가탐색영역중심이라면, 탐색을끝낸다. 만약첫번째단계에서의최소정합오차가탐색영역중심과이웃하는 8개의탐색점중에하나라면, 최소정합오차의점을중심으로이웃하는 8개의점에대해두번째단계를수행하고나서탐색을끝낸다. NTSS의자세한과정은다음과같다. Step 1) 전체 8+9=17개의점을탐색한다. 이점들은 9x9 grid 상에있는 8개의이웃하는점들과중앙의 3x3 grid 상에있는 9개의점들을의미한다. 만약최소정합오차가탐색영역중심이라면, 탐색을종료한다. 그렇지않으면 Step 2로간다. Step 2) 만약첫번째단계에서구한최소정합오차가탐색영역중앙의 3x3 grid 상에이웃하는 8개의점중에하나라면 Step 3으로가고, 그렇지않으면 Step 4로간다. Step 3) Step 1에서찾은최소정합오차의탐색점의위치에따라 3 또는 25

41 5개의점을추가해서최소정합오차의점을찾고탐색을종료한다. Step 4) Step 1에서찾은최소정합오차의탐색점을중심으로 8개의점을추가한다. 이때, 추가되는점사이의거리는첫번째단계보다반으로감소된다. 그리고 TSS의 Step 2와 Step 3를수행한다. Halfway-stop 기법에의해 NTSS는정지블록에대해서는 17개의점을탐색해야하고, 중앙에서 5x5 영역내의작은 MV에대해서는 20개내지 22개의점을탐색해야한다. 그림 2-11(d) 와같이정지블록이한개도없는경우, TSS는 25개의점을탐색하는반면 NTSS는 25+8 = 33개의점을탐색해야한다. 표 2-1은전역탐색을 1로가정한경우, NTSS와 TSS의상대적인속도비율과 MV의정확성, global minimum과 MV와의거리를나타낸것이다. MV의정확성은 TSSS의각단계에서구한움직임벡터와 global minimum의일치한정도를정량화한것이다. 표 2-1에서보는바와같이 NTSS의속도는 TSS보다더빠르고, NTSS에대한움직임벡터의정확성은 TSS보다더높다. 또한 NTSS에대한 MV와 global minimum의거리가 TSS의경우보다더작다. 이로써 NTSS 알고리즘의유효성 (validity) 과효율성 (effectiveness) 이검증된다. 26

42 (a) 탐색영역의중심 (b) 3x3 grid 상의대각선방향 (c) 3x3 grid 상의가로세로방향 (d) 9x9 grid 상 그림 NTSS 의알고리즘의예 표 2-1. TSS 와 NTSS 의비교 Speed-up ratios Probabilities Average distance Salesman Miss America Salesman Miss America Salesman Miss America TSS NTSS

43 D logarithm search [5] 2-D logarithm search(logs) 는 5x5 grid 상에서 5개의탐색점을조사한후반복적으로각탐색점의블록정합오차를비교한다음탐색범위를반으로줄여서탐색하는방식이다. 탐색윈도우 (search window) 가 7일때, LOGS 알고리즘에서는 5x5 grid상에균등하게할당된 5개의탐색점 (5-point pattern) 을이용해서최소정합오차를갖는점을찾는다. 만약최소정합오차를갖는탐색점이 5-point pattern의중심과같다면최소정합오차를갖는탐색점을중심으로 8개의탐색점을추가한다. 이때두탐색점사이의거리는초기단계의것보다반이다. LOGS 알고리즘을수행하는자세한과정은다음과같다. Step 1) 그림 2-12(a) 와같이 5x5 grid 상에균등하게위치한 5개탐색점의블록정합오차를구한다. 5개의탐색점중에서최소정합오차의점 ( 그림 2-12(a): ) 을찾는다. Step 2) 만약최소정합오차의점이그림 2-12(a) 와같이 5x5 grid 상의중심이아니라면그림 2-12(b) 와같이 Step 1의과정을반복한다. 이것은최소정합오차의점이 5x5 grid 상의중심과같을때까지반복한다. Step 3) 만약최소정합오차의점 ( 그림 2-12(c): ) 이그림 2-12(c) 와같이 5x5 grid 상의중심과같다면최소정합오차의점을중심으로 8 개의탐색 점을추가한다. 이때탐색점사이의거리는초기단계에비해반으로 28

44 감소된다. 9 개의탐색점들중에서최소정합오차를갖는탐색점의 위치가움직임벡터의좌표가된다. (a) Step 1 (b) Step 2 (c) Step 3 그림 LOGS 알고리즘의예 Block-based gradient descent search [6] Block-based gradient descent search(bbgds) 에서는오차평면상에서 global minimum이중심에집중 (center-biased) 되어있다는가정하에탐색을시작한다. 만약최소정합오차를갖는탐색점이탐색패턴의중심에존재한다면탐색을중지한다. 그렇지않으면최소정합오차를갖는탐색점을중심으로탐색을다시수행한다. 이과정은최소정합오차를갖는탐색점이탐색패턴의중심에위치하거나탐색패턴이탐색영역의경계에위치할때까지계속처리된다. 그림 2-13은 BBGDS 수행과정의예를나타낸다. BBGDS에서사용되는탐색패턴은 3x3 픽셀크기의사각형이다. BBGDS의시작단계에서는 29

45 탐색패턴의중심을원점에위치시킨다. Step 1) 그림 2-13(a) 와같이체크블록내에있는 9개탐색점의블록정합오차를구한다. 9개의탐색점중에서최소정합오차의점 ( 그림 2-13: ) 을찾는다. Step 2) 만약최소정합오차의위치가체크블록의중심이라면탐색을멈춘다. 그렇지않다면체크블록의중심이최소블록정합오차를갖는위치가될때까지최소블록정합오차를갖는위치를중심으로탐색을계속한다. 그림 BBGDS 알고리즘의예 BBGDS 는이전알고리즘들에비해탐색점이아닌체크블록단위로탐색을 하기때문에탐색점들사이에존재하는 local minimum 에빠질확률이적다. 30

46 그리고최소블록정합오차를갖는위치가체크블록의중심에존재하지않을경우체크블록에대해다시탐색을해야하지만실제로계산되는탐색점의개수는 3개내지 5개이다. 따라서체크블록단위로탐색을하지만계산량은실제로많지않다. BBGDS에서사용되는체크블록은 3x3인작은탐색패턴 (small search pattern) 이다. 따라서 BBGDS가큰움직임요소를포함하는비디오시퀀스에적용될경우 local minimum에빠질가능성이매우크다는단점이있다 Diamond search [7] Diamond search(ds) 는움직임벡터의분포는중심에집중 (center-biased) 되어있다는가정을바탕으로한다. 표 2-2는탐색윈도우의중심으로부터떨어진거리안에존재하는움직임벡터의분포확률을나타낸것이다. 표 2-2로부터약 52.76%-98.70% 의움직임벡터가탐색윈도우의중심으로부터 2픽셀안에존재한다는것을확인할수있다. 이때사용된탐색방법은 full search이고정합기준은 mean square error이다. 또한 DS에서는실제비디오시퀀스에서블록단위의움직임방향이대부분가로와세로방향이라고가정한다. 움직임의방향이가로인대표적인예에는카메라패닝 (camera panning) 이있다. DS에서는그림 2-14에나타낸바와같은두가지탐색패턴을사용한다. 첫번째탐색패턴은 large diamond search pattern(ldsp) 으로다이아몬드형태이고두번째탐색패턴은 LDSP보다더작은크기를갖는다이아몬드형태의 small 31

47 diamond search pattern(sdsp) 이다. 표 2-2. 탐색윈도우의중심주변에움직임벡터가존재할확률 Radium(pel) Tennis Football Caltrain Susie Salesman Claire (a) large diamond search pattern (LDSP) (b) small diamond search pattern (SDSP) 그림 두가지형태의탐색패턴 32

48 DS에서는최소블록정합오차가탐색패턴의중심에존재할때까지 LDSP를이용해서반복적으로탐색을한다. 만약최소블록정합오차가탐색패턴의중심에존재하면 SDSP를이용해서탐색을한다. 이때, SDSP내에최소블록정합오차를갖는탐색점의위치가예측된움직임벡터의좌표와같다. DS 알고리즘의자세한과정은다음과같다. Step 1) Search window의중심에위치한 LDSP를이용해서최소블록정합오차를갖는 search point를찾는다. 만약 winning point가중심에위치한다면 Step 3으로가고, 그렇지않으면 Step 2를수행한다. Step 2) 이전탐색단계에서찾은 winning point를중심으로다시새로운 LDSP를위치시킨다. 만약새로운 winning point가 LDSP의중심에위치한다면 Step 3으로가고그렇지않으면 Step 2를반복하여수행한다. Step 3) LDSP를 SDSP로 search pattern을변경한다. 이단계에서찾는 winning point가최종적인움직임벡터이다. 그림 2-15은 DS 알고리즘수행과정의예이다. 만약 LDSP의최소정합오차를갖는위치가다이아몬드의꼭지점에존재한다면 5개의탐색점이추가되고, LDSP의최소정합오차를갖는위치가다이아몬드의면부분에존재한다면 3개의탐색점이추가된다. 그렇지않고 LDSP의최소정합오차를갖는위치가다이아몬드의중심에존재한다면탐색패턴이 LDSP에서 SDSP로변경된다. 33

49 그림 DS 알고리즘의예 앞절에서설명한 Full search, Three step search, New three step search, Block-based gradient descent search와 Diamond search의성능을비교평가하기위하여실험을수행하였다. 실험에사용된블록의크기는 16x16이고, 탐색윈도우는 15x15이다. 사용된정합기준은 mean absolute difference(mad) 이다. 알고리즘의성능평가기준은예측된움직임벡터의정확성과계산적복잡도를사용한다. 사용된실험영상은 MPEG 성능실험에사용되는영상들이다. 예측된움직임벡터의정확성은프레임의평균 mean square error(mse) 를이용해서평가한다. 이것은표 2-3에나와있다. 그리고계산적복잡도는움직임벡터를예측하는데필요한평균탐색점의개수로써평가하고그결과는표 2-4와같다. 34

50 표 2-3. 기존의탐색방법에대한화소당평균 MSE Algorithm Tennis Caltrain Claire FS TSS NTSS BBGDS DS 표 2-4. 움직임벡터를예측하는데필요한평균탐색점의개수 Algorithm Tennis Caltrain Claire FS TSS NTSS BBGDS DS 표 2-3에서보는것과같이 "Claire" 와같은작은움직임요소의비디오시퀀스에서는 NTSS, BBGDS, DS 모두비슷한 MSE 성능을보인다. 그러나 Tennis 와같은큰움직임의비디오시퀀스에서는 NTSS, DS의성능은비슷하게유지되는반면 BBGDS의성능이크게저하되는것을확인할수있다. 이와 35

51 같이비록 BBGDS의계산량이가장적지만 BBGDS의 MSE 성능은움직임크기에의존하기때문에알고리즘의성능이안정적이지못하다. 실제비디오시퀀스에는넓은범위의움직임크기가있기때문에 NTSS, DS가사용하기에더적합하다. TSS 알고리즘은고속블록정합방법중에서가장안좋은 MSE 성능을보이는것을확인할수있다. 2.4 움직임벡터 (Motion vectors) 의결정방법 탐색방법과 COST 함수에의하여예측된움직임벡터는최종적인움직임벡터로사용될수있다. 또한움직임벡터의정확성을향상시키기위하여이미예측된움직임벡터를이용해서최종적인움직임벡터가결정될수있다. 본절에서는최종적인움직임벡터를결정하는방법에대하여설명한다 계층적 (Hierarchical) 움직임예측 [8] 계층적움직임예측방법은 lower level의프레임상에서평균값을이용해서 higher level의프레임을구성하는평균피라미드 (mean pyramid) 를이용한다. 이방법은 TSS와유사한 PSNR 성능을유지하면서계산상의복잡도를줄일수있다. 계층적움직임예측방법에서는 higher level에서 coarse 움직임벡터를정확하게찾기위하여영상피라미드는저역통과필터 (low-pass filter) 를 36

52 이용해서구성한다. 또한계층적움직임예측방법을구현하기위해 3 단계 피라미드영상은식 2-4 와같이간단한평균연산에의해구성된다. 여기서 g L ( p, q) 는 L 번째단계의위치 (p,q) 에서의화소값을나타낸다. ( p, q) g o 는 원본영상을나타낸다. 은 truncation 을나타낸다. g ( p, q) = g 1(2 p + u,2q + v),1 L 2 L L (2-4) u= 0 v= 0 그림 2-16은각단계에대한 3 단계피라미드영상의예이다. 그림 2-16에서보는것과같이 2번째단계에서의한픽셀은상대적으로 0번째단계의 4x4 block, 1번째단계의 2x2 block에대응된다. 그림 2-16에서보는것과같이 highest level은 coarsest resolution을갖고전체움직임 (global motion) 을찾기가용이하다. 또한영상의크기가줄기때문에계산상의복잡도가줄어든다. 그림 단계피라미드영상의예 37

53 계층적움직임예측방법에서정합기준으로사용되는 L 번째단계에서의 MAD는식 2-5와같다. 여기서 I와 J는블록의크기이고, ( i, ) 에서 K와 L은 g L, k j 각각 k번째프레임, L번째 level을나타낸다. 또한 I 과 J 은각각 J J '= 을의미한다. L 2 I I'= 2 L 이고 I ' J ' 1 MAD L ( m, n) = g L, k ( i, j) g L, k 1( i + m, j + n) L=0, 1, 2 (2-5) I' J ' i= 1 j= 1 m, n = 0, ± 1 평균피라미드가구성된후에먼저 2번째단계상에서움직임벡터를찾는다. 최소의 MAD L (m, n) 을갖는움직임벡터가그단계에서의 coarse 움직임벡터로선택된다. 이단계에서선택된움직임벡터는그단계에서의초기벡터로써사용되고다음하위단계로전파된다. 즉, higher level에서선택된움직임벡터는 lower level로전송되고더정확한움직임벡터로수정된다. 만약 L번째 단계에서의움직임벡터가 MV L ( r, s) 로표현된다면 L 번째단계에서선택된 움직임벡터는식 2-6과같다. 여기서 (r, s) 는탐색블록의위치를나타내고, MV L ( r, s) 는 L번째단계에서움직임변이의업데이트된증가분이다. MV ( r, s) 2 MV 1( r, s) + MV ( r, s), L L = 1, 0 = + (2-6) L L 38

54 이계층적움직임예측방법은상위단계에서전체움직임벡터를예측하기때문에 full search에비하여계산량이크게줄어든다. 그리고 TSS에비해 local minimum에빠질가능성이적다. 그러나 full search에비해 PSNR 성능이많이떨어진다 가변크기의블록을이용한움직임예측 [9] 그림 2-17은가변크기의블록을이용한움직임예측방법의블록다이어그램 (diagram) 이다. 첫번째단계에서는 8x8 블록을이용한블록정합알고리즘을기반으로각블록의움직임이추정된다. 8x8 블록의움직임벡터들은 threshold 과정과벡터미디언필터 (median filter) 에의해처리된다. 추정된움직임벡터들을이용해서움직임보상보간을수행함으로써보간된프레임이얻어진다. 가변크기의블록을이용한움직임예측방법은다양한크기의블록을이용한블록정합알고리즘을이용한다. 우선, 움직임벡터는 8x8 블록을이용한블록정합알고리즘을기반으로예측된다. 프레임영상은 8x8 블록들로나뉜다. 두프레임사이의움직임벡터는 SAD에의하여각블록마다계산된다. 39

55 Motion Estimation With 8x8 block MV s (8x8) Zero Detection + Vector Median Filter MV s (8x8) Merge [8x8] x4blocks to [16x16] N Y Motion Estimation With 16x16 block MV s (16x16) N Merge [16x16] x4blocks to [32x32] MV s (16x16) Y Motion Estimation With 32x32 block MV s (32x32) Motion Compensated Interpolation MV s (8x8) 그림 가변크기의블록을이용한움직임예측방법의블록다이어그램 작은크기의블록을이용한블록정합알고리즘을기반으로움직임벡터를 추정하는경우, 움직임벡터는잘못추정되기쉽다. 따라서본방법에서는 40

56 추정되는움직임벡터의정확성을높이기위해 zero detection 과벡터메디안 필터링 (vector median filtering) 방법을사용한다. Zero detection 방법에서는 SAD (m,n) ((x,y) (m,n) ) 과 SAD( m, n) (0) 의차가 µ 보다 작으면, 블록은정지영역에위치한다고판단한다. 그런다음움직임벡터 (, y) ( m, n) x 은 0 으로설정한다. 이때 µ 값은 190 을사용한다. 움직임벡터는이웃하는블록의움직임벡터들에의해조정된다. 본 방법에서는움직임벡터들의조정을위해벡터메디안필터링을이용한다. 움직임벡터 ( x, y) ( m, n) 에대해 3x3 의벡터메디안필터링을적용한결과인 은식 2-7 과같이정의된다. 여기서 W 는필터윈도우를나타낸다. ( x, y) ( m, n) x, y) ( m, n) = arg min ( x, y) m+ k, n+ l ( x, y) m+ i, n+ j ( k, l) W ( i, j) W ( (2-7) 그림 2-18은벡터메디안필터링을설명하기위한그림이다. 그림 2-18(a) 는 (m-1, n-1) 번째움직임벡터 ( ( x, y) m 1, n 1 ) 와주변 8개움직임벡터들을표시한 것이다. 벡터메디안필터링을하기위해서벡터 (m-1, n-1) 번째움직임벡터와 주변 8개움직임벡터에대한차이값의총합을구한다. 이와같은방법으로 3x3 윈도우 (window) 에대해수행한다. 처리하고자하는움직임벡터에대한후보값의개수는 9개이다. 만약그림 3(d) 와같이 (m, n-1) 번째움직임벡터와주변 8개움직임벡터에대한차이값의총합이최소라면, (m, n) 번째움직임벡터는 (m, n-1) 번째움직임벡터로대체된다. 41

57 (a) k=-1, l=-1 인경우 (b) k=-1, l=0 인경우 (c) k=-1, l=1 인경우 (d) k=0, l=-1 인경우 ( 최소 ) 그림 벡터메디안필터링 [3x3] 의예 그림 2-19 는벡터메디안필터링의효과를보여주는예이다. 벡터메디안 필터링을수행함으로써, 8x8 블록을이용해서추정된움직임벡터의정확성이 향상된것을확인할수있다. 42

58 (a) 벡터메디안필터링적용전의 결과영상 (b) 벡터메디안필터링적용후의 결과영상 그림 벡터메디안필터링의효과 일반적으로프레임영상에는 Global 움직임과 local 움직임이혼합되어있다. 이와같은움직임을잘표현하기위해본방법에서는움직임정도에따라다른 크기의블록을사용한다. 만약 4 개의 8x8 블록에있는움직임벡터가 비슷하다면 4 개의 8x8 블록은 1 개의 16x16 블록으로병합한다. 4 개의움직임 벡터의유사성정도는 direction distance 와 L 2 norm 에의해측정된다. Direction distance 에서는임의의두움직임벡터사이의각도를구한다. 4 개의 8x8 블록에서구한임의의두움직임벡터사이의각도개수는 6 개이다. 만약 6개의각도가모두문턱값 θ8 보다작다면, 4개의 8x8 블록을 16x16 블록으로 병합시킨다. 문턱치인 θ8 은실험을통해 30도로정한다. L 2 norm 은그림 2-20 과같이 L 2 norm 을기반으로임의의두움직임벡터 사이의거리를구한다. 구한거리의개수는 6개이다. 만약모든거리가 ε 8 보다 43

59 작다면 4 개의 8x8 블록은 16x16 블록으로병합된다. 그렇지않으면병합하지 않는다. 문턱치인ε 8 은 4로정한다. (0,0) (x 1, y 1 ) 2 Distance ( ) ( ) 2 = x 2 x1 + y2 y1 그림 두움직임벡터사이의거리 이전단계에서병합된 16x16 블록에대해움직임벡터를다시예측한다. 방법은 8x8 블록에적용된것과같다. 그리고이전단계에서 4 개의 4x4 블록을 1 개의 16x16 블록으로병합하는방법과유사하게 4 개의 16x16 블록을 1 개의 32x32 블록으로병합시킨다. 사용되는각도차이에대한문턱값은 θ16 이고, 거리 차이에대한문턱값은 ε 16 이다. 실험에의하여 θ16 는 30도로, ε 16 는 3으로 결정된다. 다음으로이전단계에서병합된 32x32 블록에대해움직임벡터를 다시예측한다. 본방법의성능을평가하기위하여세개의실험영상 (Hall monitor, Foreman, Football) 을사용해서실험하였다. 각실험영상은다른특성을갖는다. Hall monitor 는공간적으로세밀한영역과움직임을적게포함한다. 반면에, football 은 세밀한영역과움직임을많이포함한다. Foreman 은 Hall monitor 와 football 의중간 특성을갖는다. 실험영상은 50 프레임으로구성되고각프레임의크기는 44

60 352x288이다. 가변크기의블록을이용한움직임예측방법을사용해서테스트시퀀스의짝수번째프레임영상들로부터홀수번째프레임영상들을추정한다. 표 2-5는추정된프레임의평균 PSNR을나타낸다. 본방법이모든테스트시퀀스에대해가장좋은결과를보인다. 표 2-5. 생성된프레임영상의평균 PSNR [db] Proposed 8x8 block 16x16 block 32x32 block Hall monitor Foreman Football 그림 2-21은생성된결과프레임의예이다. 그림 2-21(a) 가본방법의결과영상이다. 그림 2-21(b)-(d) 는 8x8, 16x16, 32z32 블록을이용한방법에대한결과영상이다. 그림 2-21(b)-(d) 와같이고정된블록크기에의해블록경계에서블록아티팩트가발생한다. 본방법에서는이와같은블록아티팩트가줄어들었음을확인할수있다. 그림 2-22은제안하는알고리즘에의해보간된결과의예와보간된프레임상에적용된블록의크기를보여준다. 그림 2-22(b) 를보면움직임이거의없는영역에서는 32x32 블록을사용하고움직이는영역은적당한블록의크기가사용된것을확인할수있다. 본방법을적용함으로써블록 artifact가감소된다. 45

61 (a) Proposed (b) 8x8-block (c) 16x16-block (d) 32x32 block 그림 각방법에의하여생성된프레임의예 46

62 (a) 가변크기의블록을이용한움직임예측방법에의한결과영상 (b) 보간된영상에적용된블록크기의표현 그림 가변크기의블록을이용한방법에의해생성된프레임영상 47

63 2.4.3 움직임벡터의후처리 (post-processing) [1] 움직임예측단계에의하여예측된움직임벡터는 object의실제움직임을정확하게나타내지못한다. 따라서 object의실제움직임과더가까운움직임벡터를예측하기위하여움직임벡터의후처리과정이수행된다. 후처리과정에는움직임벡터필드 (field) 의메디안필터링이널리사용된다. 기존의방법 [10] 에서세로방향으로 5 블록, 가로방향으로 3 블록크기의윈도우를제안하였다. 그림 2-23은움직임벡터의후처리에사용된이웃블록의움직임벡터를나타낸것이다. 그림 2-23에서 A, B, C, D, E, F, G, X, G, H, I, J, K, L, M, N는각블록에대한움직임벡터를나타낸다. 여기서 X는현재처리하고자하는블록에대한움직임벡터이고, 나머지는이웃하는블록에대한움직임벡터를나타낸다. 움직임벡터의후처리단계를수행한후에계산된움직임벡터는식 2-8과같다. 식 2-8에서 med는메디안함수를나타낸다. [ A, B, C, D, E, F, X, G, H, I, J, K, L, M N ] D ( x, t) = med, (2-8) 움직임벡터의후처리과정은현재처리하고자하는움직임벡터는주변블록들의움직임벡터와비슷하다는가정하에수행된다. 식 2-8의후처리과정을통하여주변움직임벡터와큰차이를보이는움직임벡터는수정된다. 따라서자막등과같이주변움직임벡터가유사한영역에서효과가크다. 48

64 y-2y y-y y y+y y+2y A B C D E F G X H I J K L M N x-2x x x+2x 그림 움직임벡터의후처리과정에사용된움직임벡터 49

65 3. 기존의프레임보간 (Frame interpolation) 방법 [11] 3.1 Temporal weighted averaging Temporal weighted averaging 방법은움직임벡터를이용하지않는가장기본적인프레임보간방법으로서이전프레임과현재프레임의평균에의하여계산된다. 식 3-1은 temporal weighted averaging을계산하는수식을나타낸다. 식 3-1에서 n-p는보간될프레임의인덱스이고, n-k와 n은각각이전프레임과현재프레임을나타내는인덱스이다. 1 F avg > k ( x n p) = ( p F( x, n k) + ( k p) F( x, n) ); p > 0, k p, (3-1) 예를들어프레임변환방법의결과가현재프레임수의두배이면 k=2, p=1이다. 이방법은영화자막같은고정된영상에서 blur없는영상을획득할수있지만움직이는영상에서는 blur현상이발생한다. 그림 3-1은 Temporal weighted averaging 방법을적용한결과영상을나타낸다. 실험에사용된영상은일정한속도로왼쪽에서오른쪽으로이동하는장면이고, 영상의하단부분에있는텍스트는정지된것이다. 그림 3-1에서보는것과같이고정되어있는텍스트는선명하게표현되는반면움직이는배경부분은심하게 blur되어표현된다. 50

66 51 그림 3-1. Temporal weighted averaging 방법을적용한결과영상 3.2 Motion compensation average Motion compensation average 방법은움직임벡터를사용하는기본적인방법으로서움직임벡터를이용하여이전프레임과현재프레임을평균하는방법이다. 식 3-2 는 Motion compensation average 방법에의한프레임보간방법을나타낸다. 식 3-2 에서 D 는예측된움직임벡터를나타낸다. ( ) ( ) p k p n k D p x F p k k n k D p k x F p k p n x F mca > > + + = 0, ;,, 1 ), (

67 (3-2) 그림 3-2는 motion compensation average 방법을적용한결과영상을나타낸다. 나무가지와같이움직이는영역이깔끔하게표현된것을확인할수있다. 그림 3-3은결과영상의텍스트부분을확대시킨것이다. 그림 3-3을보는것과같이잘못예측된움직임벡터에의하여텍스트가제대로표현되지못한것을확인할수있다. 즉, 본방법은예측된움직임벡터의성능에의하여결과영상의화질이크게좌우된다. 그림 3-2. Motion compensation average 방법을적용한결과영상 52

68 그림 3-3. Motion compensation average 방법에의한정지텍스트에서의 artifact 3.3 Static median filtering Static median filtering 방법은식 3-3과같이이전프레임의픽셀값, 현재프레임의픽셀값, 움직임에의해보상된프레임의픽셀값중에서중간값을출력으로결정한다. 식 3-3에서 MEDIAN(.) 은입력값중에서중간크기에해당되는값을출력하는함수이다. Motion compensation averaging 방법에의해보상된프레임값은식 3-2에나타낸것과같이이전프레임과현재프레임의사이의값을가질경우에만출력이된다. 따라서영화자막과같이이전프레임과현재프레임의값이유사한경우에는이전혹은현재프레임의값이출력된다. F sta ( x n p) = MEDIAN( F( x, n k), F( x, n), F ( x, n p) ), (3-3) mca 그림 3-4 는 static median filtering 을적용한결과영상을나타낸다. Static median filtering 에의한결과영상은 motion compensation averaging 방법에의한결과 53

69 영상에비하여텍스트부분은잘표현되는반면나무가지와같은세밀한영역은제대로표현되지않는것을확인할수있다. 그림 3-5는 static median filtering에의한영상에서정지텍스트와움직이는에지에서의화질향상을보여준다. 그림 3-4. Static median filtering 방법을적용한결과영상 54

70 그림 3-5. Static median filtering 방법에의한정지텍스트에서의화질향상 3.4 Dynamic median filtering Dynamic median filtering 방법은식 3-4에나타낸것과같이움직임에따른이전프레임픽셀값, 움직임에따른현재프레임픽셀값, 현재위치에서의두프레임의평균값중에서중간값을출력한다. 추출된움직임벡터가정확하다면움직임에따른이전프레임픽셀값과움직임에따른현재프레임픽셀값은유사할것이다. 식 3-4는움직임에따른이전프레임픽셀값또는움직임에따른현재프레임픽셀값을출력한다. 만약움직임에따른이전프레임픽셀값과움직임에따른현재프레임픽셀값이유사하지않다면추출된움직임벡터는잘못된것일확률이크다. F dyn ( x, n p) = MEDIAN F x + ( k p) k D, n k, F x p D, n, F k avg ( x, n p) (3-4) 55

71 그림 3-6은 dynamic median filtering 방법을적용한결과영상을나타낸다. Dynamic median filtering에의한결과영상은 motion compensation average 방법에의한결과영상에비하여상당한화질향상을보인다. 특히움직이는세밀한배경부분상에있는텍스트와같은고정된 object에서향상된화질을보인다. 그림 3-7은그림 3-6의텍스트부분을확대시킨영상이다. 이방법의문제점은매우세밀한영역의 edge에서톱니현상이발생하는것이다. 그림 3-6. Dynamic median filtering 방법을적용한결과영상 56

72 그림 3-7. Dynamic median filtering 방법에의한정지텍스트에서의화질향상 이방법의또다른문제점은제한된선택의수이다. 만약움직임벡터가부정확하다면 temporal weighted averaging이선택될것이다. 그러나이것은모든경우에대해최적의결과가아니다. 예를들어움직이는배경상에움직이는 object가존재하는경우정확한움직임벡터를예측하기어렵기때문에 motion compensated 픽셀값과 temporal weighted averaging 픽셀값이모두적절하지않게된다. 따라서보간오차와움직임 blur의문제점이발생할것이다. 이경우에는 motion compensated 픽셀값과 temporal weighted averaging 픽셀값의평균을하는것이더좋은성능을보인다. 3.5 Soft switching Soft switching 방법은움직임을고려한두프레임간의평균값과움직임을 고려하지않은두프레임간의평균값에대한가중된평균 연산 (weighted average) 을수행한다. 가중치는주변움직임벡터를고려하여결정한다. 식 3-5 는 Soft switching 방법을계산하기위한수식이다. 식 3-5 에서 c 는움직임벡터의 57

73 지역적신뢰도로서 c 의값이작을수록예측된움직임벡터의정확도가높은 것을의미한다. F ( x, n p) = c F + ( 1 c) F ; 0 c 1 mix avg mca (3-5) Local vector smoothness(lvs) 는 c 의값을조절하는데사용되는유용한 변수이다. LVS 는식 3-6 에의하여정의된다. 식 3-6 에서 x b, y b 는블록의가로 세로위치를나타내고, Ind 는중간변수이다. Dx b y b 는블록 B(x b, y b ) 에대한 움직임벡터를나타내고, α>0, 0 β 1이다. LVS는움직임벡터의부드러움 (smoothness) 이나연속성 (continuity) 의측정값이다. 대상의움직임이잘예측된경우, 움직임벡터들의공간상관도는높다고가정한다. 반면복잡한움직임이나대상의경계와같이움직임이잘예측되기어려운경우, 움직임벡터들의영역에는불연속점이존재할것이다. 식 3-7에서 MIN(.) 은입력변수들에대한상한선을정하는함수이다. LVS( x xb b, y b = ) y + 1 b i= xb 1 j= yb 1 D ij D xb yb x, y (3-6) (,1) ( x y ) MIN LVS( x, y ) Ind = (3-7) b, b b b 58

74 ( x, y ) b b ( x, y ) Ind b b = MIN, β α c (3-8) 이방법은 dynamic median filter 방법보다결정오차에대하여완화되었기때문에적응성 (flexibility) 이더좋다. 따라서더향상된주관적인화질을보일가능성이크다. 그러나이방법은움직임벡터의정확성을판단하는 LVS 함수에따라성능이좌우된다는제약을갖는다. 또한불필요한모션져더나블러와같은문제점이발생될수있다. 3.6 Cascaded median filters Cascaded median filter 방법은식 3-9와같이나타낼수있다. 식 3-9에서 F mix, F dyn, 그리고 F sta 은각각 soft switching 방법, dynamic median filtering 방법, 그리고 static median filtering 방법에의한결과를나타낸다. 따라서식 3-9와같이 F mix, F dyn, 그리고 F sta 의중간값을출력값으로결정하면, 일반적인영상에서 F mix 의값을출력하고세밀한영역에서는 F sta 의값을출력한다. 그리고영화자막의경우에는 F dyn 의값이제일작거나커지므로 F sta 을이용하여결과값을보정한다. Mix filter는움직이는대상의에지주변에서주로선택될것이다. 왜냐하면 local 부드러움이벡터영역내의불연속점 (discontinuity) 에의해감소되기때문이다. out ( F, F F ) F MEDIAN, = (3-9) dyn sta mix 59

75 그림 3-8은실험시퀀스의한프레임을나타낸다. 그림 3-9는그림 3-8에대하여 cascaded median filter에서선택된요소를표현한그림이다. 그림 3-9에서흰색은 static과 dynamic median의출력값이동일한영역을나타내고, 밝은회색은모든입력값이동일한영역을나타낸다. 또한어두운회색은 dynamic median이선택된영역을나타내고, 검은색은 mix input이선택된영역을나타낸다. 그림 3-9의왼쪽사람의경계를따라서 mix input이선택된것을확인할수있다. 매우세밀한부분인식물영역은 dynamic median이선택된다. 비록 mix 출력영상의화질이더좋을지라도메디안연산에의하여최적의값은선택될수없다. 이것이 cascaded median filters의단점이다. 60

76 그림 3-8. 실험시퀀스의한프레임 61

77 그림 3-9. 실험프레임상에선택된신호의분포 62

78 4. 제안하는움직임예측방법 제안하는움직임예측방법은대상의움직임정도에따라서가변크기의블록과탐색영역을사용한다는특징을갖는다. 또한제안하는방법은휴대폰을대상으로개발되었기때문에사용되는계산량과하드웨어의복잡도가낮다는특징을갖는다. 제안하는움직임예측방법에서는먼저각프레임 (frame) 의트랜지션 (transition) 여부를결정한다. 트랜지션타입 (type) 은장면전환과같이인접프레임간의변화가큰프레임을의미한다. 그림 4-1은프레임의트랜지션여부에따른프레임레이트변환방법을나타낸다. 프레임이트랜지션타입인경우에는움직임예측단계를거치지않고프레임보간단계를수행한다. 트랜지션타입인프레임에서예측된움직임벡터의정확도가낮기때문에결과영상의화질이좋지않다. 트랜지션타입이아닌경우에는제안하는움직임 예측방법에의해예측된움직임 벡터를이용해서프레임보간단계를 수행한다. 식 4-1은트랜지션타입의경우수행되는프레임보간방법을나타내는식이다. 식 4-1에서 f ( x, y) 는 (x, y) 위치에있는픽셀값이고 α 는 0과 1사이의상수이고, 블록의가로, 세로크기이며 n은프레임의인덱스이다. 1 F( x, n ) = α F( x, n 1) + (1 α) F( x, n) 2 (4-1) 63

79 Reference Frame Current Frame Calculate the frame difference Data flow Control flow Transition type? Y N Proposed motion estimation Frame interpolation 그림 4-1. 제안하는프레임레이트변환방법의전체흐름도 그림 4-2는제안하는움직임예측방법의전체순서도이다. 먼저이전프레임과현재프레임의동일위치에있는 16개의 8x8 블록의픽셀값이입력된다. 입력된픽셀값으로써 16개의 8x8 블록에대한움직임활동도 (motion activity level) 가예측된다. 다음으로예측된움직임활동도에의하여블록과탐색윈도우의크기가결정된다. 결정된블록과탐색윈도우의크기를기반으로블록정합방법이수행되고각블록에대한예측된움직임벡터가저장된다. 아래각단계에대한자세한설명이제시되어있다. 64

80 Input the sixteen neighboring 8x8 blocks in previous frame and current frame Estimate the motion activity level for each of sixteen 8x8 blocks Determine the sizes of block and search window Estimate the motion vector of each block using block matching algorithm Store the motion vectors 그림 4-2. 제안하는움직임예측방법의순서도 4.1 각블록에대한움직임활동도의예측단계 블록의움직임활동도는그블록에대한움직임의정도를나타낸다. 블록의 움직임활동도는식 4-2 와같이현재프레임과이전프레임의동일위치에있는 블록들사이의 SAD에의해서예측된다. 식 4-2에서 F( x, n) 은 n번째프레임의 (x, y) 위치에있는픽셀값이고 B(X ) 은 8x8 블록에해당되는위치이다. 65

81 x B( X ) ( x, n) F( x 0, n 1) BD (0, X, n) = F (4-2) 블록타입은그림 4-3 과같이계산된움직임복잡도에의하여결정된다. 블록 사이의 SAD 값이 TBlowerr 보다작은경우에블록은움직임이거의없는 nomotion 타입으로결정되고그렇지않은경우에는블록은움직임이있는 motion 타입으로정한다. 결정된블록타입을사용해서움직임예측에사용되는블록의 크기가결정된다. Calculate the block difference with 8x8 block(bd) Determine as no-motion type Y N Determine as BD> TB lowerr? motion type 그림 4-3. 블록타입을결정하는방법의순서도 제안하는방법에서는 SAD의연산을이용해서움직임활동도가예측된다. 기존의가변크기의블록을이용한움직임예측방법에서는각 8x8 블록에대하여움직임벡터가예측을한다음, 이웃하는움직임벡터의유사도에의하여이웃하는 8x8 블록들이 16x16 블록으로병합될지의여부가결정된다. 또한 16x16 블록에대하여다시움직임예측과정이수행된다음, 16x16 블록에대하여예측된움직임벡터를사용해서이웃하는 16x16 블록들이 32x32 66

82 블록으로병합될지의여부가결정된다. 이와같이기존의가변크기의블록을사용하는움직임예측과정에서는블록의크기를결정하는과정에서움직임예측과정을반복적으로수행하기때문에움직임예측과정에서필요한계산량이상당히많다. 따라서이기존의방법은휴대폰에서의실시간처리에적합하지않다. 그러나제안하는방법에서는블록의크기를결정하기위하여간단한 SAD 연산을사용하기때문에계산량이적고하드웨어적복잡도가낮다. 따라서제안하는방법은휴대폰을대상으로하기에적합하다. 결정된움직임타입은다음단계에서블록과탐색윈도우의크기를결정하기위하여사용된다. 4.2 블록과탐색윈도우크기의결정단계 블록의크기는전단계에서결정된블록타입에의하여블록클래스로구분된다. 블록클래스는이웃하는 8x8 블록들의블록타입에의해결정된다. 그림 4-4는각블록클래스와이에속하는블록의크기를나타낸다. 예를들어그림 4-4(B) 는두번째클래스를나타내고그림 4-4(b) 는두번째클래스에속하는블록의종류를나타낸것이다. 각클래스에속하는블록의종류에서숫자 1은 no-motion 타입을나타내고, 2는 motion 타입을나타낸다. 만약이웃하는블록들이 no-motion 타입이라면그블록들은더큰블록으로병합된다. 예를들어 4개의 8x8 블록이모두 no-motion 타입인경우 4개의 8x8블록은 1개의 16x16블록으로병합된다. 제안하는방법에서사용되는블록의크기는 8x8, 16x8, 8x16, 16x16, 32x32이다. 67

83 (A) class 1 (16x16) (a) Block in the class (B) class 2 (8x8) (b) Blocks in the class (C) class 3 (16x8, 8x8) (c) Blocks in the class (D) class 4 (16x8, 8x8) (d) Blocks in the class

84 (E) class 5 (8x16, 8x8) (e) Blocks in the class (F) class 6 (8x16, 8x8) (f) Blocks in the class (G) class 7 (32x32) (g) Block in the class 7 그림 4-4. 제안하는움직임예측방법에서사용된블록클래스 그림 4-5는제안하는방법에의해보간된프레임상에적용된블록의크기를나타낸다. 그림 4-5(a) 의테스트영상은왼쪽에서오른쪽으로프레임간격당 2 화소의속도로이동하는사각형과같은단순한움직임의대상을포함한다. 그림 4-5(b) 의테스트영상은복잡한움직임의대상을포함한다. 블록의크기는움직임예측의성능에큰영향을주는요소이다. 움직임이거의없는영역에서는비교적큰크기의블록이사용되고, 움직임이많은영역에서는비교적작은크기의블록이사용되는것이적합하다. 그림 4-5를보면움직임이거의없는배경영역에서는 32x32 블록이사용되고움직임이있는영역에서는 69

85 더작은크기의블록이사용된것을확인할수있다. (a) artificial video sequences (b) bubble video sequences 그림 4-4. 보간된영상에적용된블록크기의표현 탐색윈도우의크기는이미결정된블록의타입에의해정해진다. 각블록 70

86 타입에따라사용되는탐색윈도우의크기는표 4-1과같다. 블록의움직임복잡도가큰경우에사용되는탐색윈도우의크기도크다. 반면에블록의움직임이거의없는 no-motion 타입인경우에는사용되는탐색윈도우의크기가상대적으로작다. 따라서제안하는방법에서는블록타입에따라탐색윈도우의크기를다르게사용함으로써계산량이감소된다. 표 4-1. 블록타입에따라사용되는탐색윈도우의크기 블록타입 탐색윈도우 no-motion ± 2 motion ± 움직임벡터의예측단계 그림 4-6은제안하는움직임벡터를예측하는방법에대한순서도이다. 먼저이전단계에서결정된블록과탐색윈도우의크기를이용해서 backward 움직임예측과정이수행된다. Backward 움직임예측에서는현재프레임이참조 (reference) 프레임으로써사용된다. 사용된정합오차기준은식 4-3과같이 SAD이고, 움직임벡터는식 4-4의식에의하여예측된다. 여기서 D( X, n) 는예측된움직임벡터를의미한다. 71

87 ( C, X, n) = F( x, n) F( x C, n 1) SAD (4-3) D( X, n) arg min x B( X ) C S { SAD( C, X, n) } = (4-4) Process the backward motion estimation using determined size of block and search window Count the number of case, ( C, X, n) SAD( D, X, n) TSAD SAD < Number of case < Y Tnum Zero motion detection N Process the forward motion estimation Check the minimum SAD Minimum SAD<T SAD Y Store the motion vectors N Motion Estimation with expanded adaptive search window 그림 4-5. 제안하는움직임벡터의예측단계 72

88 Backward 움직임예측과정이수행될때탐색윈도우에있는각위치에서의 블록과현재처리하고자하는블록사이의 SAD 값인 SAD ( C X, n) SAD 값인 SAD ( D X, n), 와최소, 가계산된다. 탐색윈도우상에최소 SAD 값과 유사한 SAD 값을갖는위치가많은경우, 탐색윈도우상의계산된 SAD 분포에는다수의 local minimum 이존재할가능성이크다. 따라서식 4-5 의 조건에해당되는경우에는 forward 움직임예측과정이수행된다. 여기서 T SAD 는 미리결정된 threshold 값이다. ( C X, n) SAD( D, X, n) TSAD SAD, < (4-5) Forward 움직임예측에서는 Backward 움직임예측에서의참조방향과반대로 이전프레임이참조 (reference) 프레임으로써사용된다. 자막과같이한방향으로 움직이거나정지된대상에적용되는경우, 탐색윈도우상의계산된 SAD 분포에다수의 local minimum 이존재한다. 이와같은경우에발생되는문제점을 해결하기위하여이전프레임과현재프레임의동일위치에존재하는블록의 움직임이유사하다는가정하에 forward 움직임예측이수행된다. 그림 4-7 은프레임의경계 (boundary) 부분에해당되는자막의예를나타낸다. 이자막은오른쪽에서왼쪽으로같은속도의움직임을갖고그림 4-7 의오른쪽 경계가프레임의경계에해당된다. 그림 4-7 에서사각형테두리안의블록이 73

89 현재처리하고자하는블록이라고가정하자. Backward 움직임예측에서는그림 4-7(b) 의사각형테두리안의블록이기준으로써사용되고이전프레임상에서탐색이수행된다. 그러나그림 4-7(b) 의사각형테두리안의블록은이전프레임상에는없던대상을포함하기때문에이전프레임상에서는처리하고자하는블록과정확하게정합되는블록을찾는것이거의불가능하다. 따라서이전프레임상의블록이기준으로써사용되고현재프레임상에서탐색이수행됨으로써처리하고자하는블록과정확하게정합되는블록이결정될수있다. 이전프레임 (n-1 번째프레임 ) 현재프레임 (n 번째프레임 ) 그림 4-6. Forward 움직임예측에효과적인자막부분의예 74

90 실제움직임벡터의값은 (0, 0) 임에도불구하고움직임벡터의값이 (0, 0) 이아닌다른값으로예측되는경우가있다. 이와같은현상을보정하기위해정지 움직임검출 (zero motion detection) 단계를수행한다. 이단계에서는 SAD ( D X, n) (, X n), 과 SAD 0, 의차가미리결정된임계값보다작으면, 블록은정지영역에 위치한다고판단하고움직임벡터 ( X n) D, 은 (0, 0) 으로설정한다. 여기서 0 은 (0, 0) 을나타낸다. 제안하는방법에서는속도를향상시키기위해초기에사용된탐색윈도우의크기가작다. 만약대상의움직임크기가초기에사용된탐색윈도우의크기보다크다면움직임벡터를잘못예측할가능성이크다. 따라서이와같은경우를보정하기위해더큰탐색윈도우상에서탐색하는것이필요하다. 현재프레임상의처리하고자하는블록과이전프레임상에서예측된블록사이의 SAD 값이미리결정된임계값보다큰경우, 확대된탐색윈도우상에서탐색이다시수행된다. 이단계에서는확대된탐색윈도우상에서이미탐색된영역을제외한나머지영역에대하여탐색이수행되기때문에실행시간이오래소요되지않는다. 75

91 5. 제안하는프레임보간방법 제안하는프레임보간단계에서는예측된움직임벡터를이용해서새로운프레임이생성된다. 그림 5-1은제안하는프레임보간방법의순서도를나타낸다. 먼저예측된움직임벡터를이용하여현재처리하고자하는블록의 움직임벡터신뢰도 RSAD ( D X, n), 가식 5-1 에의하여계산된다. 제안하는 방법에서는 motion compensation average (MCA) 방법을사용해서새로운프레임이생성된다. MCA 방법에의해보간된블록들이유사할수록예측된움직임벡터의 신뢰도는높아지고 RSAD ( D X, n), 의값은작아진다. D D RSAD ( D, X, n) = F x +, n F x, n 1 (5-1) x B( X ) 2 2 계산된 RSAD ( D X, n), 가미리결정된 threshold 값보다작은경우, 예측된 움직임벡터를이용해서 MCA 방법에의하여새로운프레임이생성된다. 그렇지않은경우, 처리하고자하는블록과이웃하는블록들에대한움직임 벡터의신뢰도가식 5-2 에의하여계산된다. 식 5-2 에서 dx 의값은 (-8, 0), (8, 0), (0, -8), (0, 8) 과같다. 즉, X + dx 네개블록의중심위치를의미한다. 는처리하고자하는블록과상하좌우로인접한 76

92 D D RSAD ( D, X + dx, n) = F x +, n F x, n 1 (5-2) x B( X + dx ) 2 2 Input the estimated motion vector (MV) Calculate the estimated MV reliability Is the MV reliable? Y Calculate the MV reliability of neighboring N blocks Y Is the MV of neighboring blocks unreliable? Change the estimated MV to reliable MV N Interpolate the frame using MCA 그림 1-2. 제안하는프레임보간방법의순서도 이웃하는네개의블록에대한움직임벡터신뢰도가계산된후에가장 작은 RSAD ( D, X + dx, n) 값에해당되는블록을찾는다. RSAD ( D X, n), 가 77

93 ( D X dx n) RSAD, +, 의최대값보다큰경우, 이웃하는블록의움직임벡터가 처리하고자하는블록의움직임벡터보다더신뢰할수있다고판단한다. 처리하고자하는블록에대한움직임벡터는최소 RSAD ( D X dx, n), + 의블록에 해당되는움직임벡터로대체된다. 그런다음변경된움직임벡터를이용해서 MCA에의하여새로운프레임이생성된다. ( D, X n) 가 RSAD ( D X dx, n) RSAD,, + 의최대값보다작은경우, 처리하고자하는 블록의움직임벡터가이웃하는블록의움직임벡터보다더신뢰할수있다고판단한다. 그리고처리하고자하는블록의움직임벡터를이용해서 MCA에의하여새로운프레임이생성된다. 식 5-3은 MCA를수행하는식을나타낸다. 1 1 D D F mca ( x, n ) = F x +, n + F x, n 1 (5-3)

94 6. 실험결과 본논문에서는여섯개의테스트시퀀스영상 ( Hall monitor, Football, Foreman, Table tennis, Flower garden, Coastguard ) 을사용해서실험하였다. 각실험영상은다른특성을갖는다. Hall monitor 는세밀한영역을적게포함하고대상의움직임이크지않다. 반면에, Football 은세밀한영역을많이포함하고대상의움직임이크다. Foreman 은 Hall monitor 와 Football 의중간특성을갖는다. Table tennis 는확대, 카메라패닝 (panning), 장면전환과같은컨텐트 (content) 를포함한다. Flower garden 은카메라패닝과같은단순한움직임을포함하고, Coastguard 는반대방향으로이동하는두대상을포함한다. 각테스트시퀀스는 100프레임으로구성된다. Foreman 과 Coastguard 에해당되는각프레임의크기는 352x288이고, 나머지테스트시퀀스에해당되는각프레임의크기는 352x240이다. 실험에서는테스트시퀀스의짝수번째프레임영상이입력된다. 입력된짝수번째프레임으로부터프레임레이트변환방법에의하여홀수번째프레임영상들을생성한다. 제안하는방법과의성능비교를위하여사용된기존의움직임예측방법은고정된크기의블록과탐색영역을사용하는 full search와고속움직임예측방법인 three step search[3], 그리고가변크기의블록을이용한움직임예측방법 [9] 이다. 실험에사용된프레임보간방법은 motion compensation averaging[11] 이다. 기존의움직임예측에대한실험에사용된 79

95 블록의크기는 8x8 이고, 탐색윈도우는 x 와 y 방향으로최대 6 픽셀 (w=6) 이다. 본논문에서는기존의방법과제안하는방법의객관적인성능 평가를 수행하기위하여 PSNR 수치를사용한다. 식 6-1은 PSNR을계산하는식이다. 식 6-1에서 PxQ는프레임의크기이고, g(p, q) 와 g r (p, q) 는각각원영상과결과영상내에 (p, q) 위치에서의픽셀값을의미한다. 본실험에서는테스트시퀀스의홀수번째프레임이원영상과같고, 프레임레이트변환방법에의하여생성된홀수번째프레임이결과영상에해당된다 PSNR = 10 log 2 / PQ [ g( p, q) g r ( p, q) ] 10 (6-1) p q 표 6-1은블록정합방법에따른각블록당움직임벡터를예측하는데필요한총연산수를나타낸다. K는정합오차를계산하는데필요한픽셀당연산의수를나타낸다. NxN은블록의크기를의미한다. 탐색영역이 13x13이기때문에 full search의경우탐색되는위치의수는 169이다. TSS의경우탐색되는위치의수는 25이다. TSS의계산량은 full search에비하여 0.148배정도적다. 표 6-1의계산량은탐색영역내에서탐색되는위치의수에의하여결정되는것이다. 80

96 표 1-2. 기존블록정합알고리즘의계산량비교 알고리즘 FS TSS Sub-block 계산량 169KN 2 25KN KN 2 그림 6-1은기존의고속블록정합방법과제안하는방법에대한 PSNR 값을그래프로나타낸것이다. 그림 6-1에서가로축은프레임순서를나타낸것이고, 세로축은계산된 PSNR 값을나타낸다. 그림 6-1에서보는것과같이제안하는방법의성능이기존의방법에비하여더뛰어난것을확인할수있다. 특히기존의고속블록정합방법인 TSS 방법은 full search 방법에비하여성능이상당히안좋다. (a) Foreman sequences 81

97 (b) Football sequences (c) Hall monitor sequences 82

98 (d) Table tennis sequences (e) Flower garden sequences 83

99 (f) Coastguard sequences 그림 1-2. 기존의고속블록정합알고리즘과제안하는방법의성능비교 표 6-2과표 6-3은제안하는방법과 full search의계산적복잡도를프레임별로비교한것이다. 여기서전역탐색에서사용된블록의크기는 8x8이고탐색윈도우의크기는 ± 7이다. 사용된테스트시퀀스는비교적적은움직임을갖는 artificial 시퀀스와비교적많은움직임을갖는 bubble 시퀀스이다. 테스트시퀀스의크기는 352x256이다. 표 6-2과표 6-3에서 Frame # 은프레임의번호를나타내고, Slow # 과 Normal # 은상대적으로각프레임내에서 no-motion type과 motion type으로결정된블록의개수를나타낸다. 제안하는방법에대한계산량은식 6-2에의해계산되고 full search에대한계산량은식 6-3에의해 84

100 계산된다. 표 6-2 과표 6-3 에서보는것과같이제안하는방법에서사용된계산 량이 full search 에서사용된계산량보다적은것을확인할수있다. 제안하는방법에대한계산량 = (slow #)*(search window of slow type) 2 + (normal #)*(search window of normal type) 2 (6-2) Full search에대한계산량 = (total number of block in the frame)*(search window of slow type) 2 (6-3) 표 3-4. 제안하는방법과 full search의계산량비교 ( 테스트시퀀스 : artificial video sequences) Frame # Proposed method Full search Slow # Normal # 계산량계산량 Proposed/FS

101 표 5-6. 제안하는방법과 full search 의계산량비교 ( 테스트시퀀스 : bubble video sequences) Frame # Proposed method Full search Slow # Normal # 계산량계산량 Proposed/FS 제안하는방법에서는 no-motion type인경우, 사용되는탐색윈도우의크기가상대적으로작다. 따라서테스트시퀀스의움직임이작을수록제안하는방법에서필요한계산량이감소한다. 표 6-4는탐색윈도우의중심으로부터떨어진거리안에존재하는움직임벡터의분포확률을나타낸것이다. 이때사용된탐색방법은 full search이고정합기준은 summed square error이다. 표 6-4로부터약 52.76%-98.70% 의움직임벡터가탐색윈도우의중심으로부터 2 픽셀안에존재한다는것을확인할수있다. 따라서제안하는방법을사용하는경우계산적복잡도가크게감소되는장점이있다. 86

102 표 7-8. 탐색윈도우의중심으로부터떨어진거리안에움직임벡터가존재할 확률 [7] Radium(pel) Tennis Football Caltrain Susie Salesman Claire 그림 6-2는기존의가변크기의블록을이용한움직임예측방법과제안하는방법에대한 PSNR 값을그래프로나타낸것이다. 기존의가변크기의블록을이용한움직임예측방법 (adaptive ME) 은기존의블록정합알고리즘에비하여좋은성능을보인다. 하지만그림 6-2에서보는것과같이제안하는방법의성능이기존의 adaptive 블록크기를이용한움직임예측방법에비하여더좋은것을확인할수있다. 또한기존의가변크기의블록을이용한움직임예측방법은제안하는방법에비하여계산량이더많다는단점을갖는다. 87

103 (a) Foreman sequences (b) Football sequences 88

104 (c) Hall monitor sequences (d) Table tennis sequences 89

105 (e) Flower garden sequences (f) Coastguard sequences 90

106 그림 3-4. 기존의가변크기의블록을이용한움직임예측방법과제안하는 방법의성능비교 PSNR의계산이간편하고, 그것의물리적의미가명확하기때문에 PSNR은객관적화질평가기준으로널리사용되고있다. PSNR은주관적화질평가의결과와의상관성이적다 [12]. 인간시각시스템 (Human visual system) 은영상을픽셀단위로처리하지않고, 영상의공간적, 시간적, 그리고색상등을받아들이기때문이다. 따라서제안하는방법의성능을평가하기위하여주관적화질평가도중요한역할을한다 [13]. 그림 6-3, 6-4와 6-5은기존의방법과제안하는방법에의하여생성된프레임을나타낸다. 그림 6-3, 6-4와 6-5에서보는것과같이기존의가변크기의블록을이용한움직임예측방법과제안하는방법에의한결과영상은거의비슷한화질을갖는다. 반면기존의 full search 방법과 TSS 방법에의한결과영상은제안하는방법에의하여생성된결과영상에비하여블록아티팩트와모션블러가심하게발생하기때문에화질이좋지않다. 91

107 (a) Full search (b) TSS 92

108 (c) 기존의가변크기의블록을이용한움직임예측방법 (d) 제안하는방법 그림 5-6. 기존의방법과제안하는방법의화질평가 (Foreman) 93

109 (a) Full search (b) TSS 94

110 (c) 기존의가변크기의블록을이용한움직임예측방법 (d) 제안하는방법 그림 7-8. 기존의방법과제안하는방법의화질평가 (Football) 95

111 (a) Full search (b) TSS 96

112 (c) 기존의가변크기의블록을이용한움직임예측방법 (d) 제안하는방법 그림 기존의방법과제안하는방법의화질평가 (Flower garden) 97

113 7. 결론 본논문의목적은휴대폰프로젝션디스플레이상에서디스플레이되는 T- DMB의화질을향상시키기위하여효과적인프레임레이트변환기술을개발하는것이다. 또한본논문에서제안하는프레임레이트변환기술은휴대폰프로젝션디스플레이를대상으로하기때문에제안하는기술은간단한하드웨어복잡도와계산량으로구현된다는특징을갖는다. 본논문에서제안하는움직임예측방법은대상의움직임활동도에따라다른크기의블록을사용하는특징을갖는다. 블록의크기는움직임예측기술의성능을결정하는중요한요소이다. 움직임이거의없는영역에서는비교적큰크기의블록이사용되고, 움직임이많은영역에서는상대적으로작은크기의블록이사용된다. 실험을통하여제안하는방법에의한결과영상의화질이고정된크기의블록을사용하는 full search에의한결과영상에비하여훨씬뛰어난것을확인할수있다. 또한정지된배경과같이대상의움직임이상대적으로작은영역에대하여작은크기의탐색윈도우를사용함으로써 full search 방법에비하여필요한계산량이적다. 또한 3채널칼라영상의경우, 제안하는방법에서는 Red, Green, Blur 채널에대하여각 1개의프레임메모리가필요하다. 이와같이제안하는방법은하드웨어복잡도가간단하기때문에실시간비디오처리에적용될수있다. 복잡한움직임을포함하는비디오시퀀스에서는정확한움직임벡터를 98

114 예측하기가어렵다. 특히새로운대상등장하거나사라지는 occlusion 의 경우에는움직임벡터를예측하는것이어렵다. 따라서이와같은문제를 해결하고더정확한움직임벡터를예측하기위한추후연구가필요하다. 99

115 8. 참고문헌 [1] G. de Hann, Motion estimation and compensation an integrated approach to consumer display field rate conversion, Eindhoven, Natuurkundig Laboratorium, 1992 [2] Bede Liu and Andre Zaccarin, New fast algorithms for the estimation of block motion vectors," IEEE Trans. Circuits Syst. Video Technol., vol. 3, pp , April [3] T. Koga, K. Iinuma, A. Hirano, Y. Iijima, and T. Ishiguro, Motion-compensated interframe coding for video conferencing, in Proc. NTC 81, pp. C , New Orleans, LA, Nov./Dec [4] R. Li, B. Zeng, and M. L. Liou, A new three-step search algorithm for block motion estimation, IEEE Trans. Circuits Syst. Video Technol., vol. 4, pp , Aug [5] J. R. Jain and A. K. Jain, Displacement measurement and its application in interframe image coding, IEEE Trans. Commun., vol. COM-29, pp , Dec [6] Lurng-Kuo Liu and Ephraim Feig, A block-based gradient descent search algorithm for block motion estimation in video coding, IEEE Trans. Circuits Syst. Video Technol., vol. 6, pp , Aug [7] Shan Zhu and Kai-Kuang Ma, "A new diamond search algorithm for fast blockmatching motion estimation," IEEE Trans. Image processing, Vol. 9, pp , Feb [8] Kwon Moon Nam, Joon-Seek Kim, Rae-Hong Park and Young Serk Shim, A fast 100