#1. [H.264] 동영상 압축의 기본 개념
#2. [H.264] 동영상 압축의 기본 개념 – RGB, YCbCr, 서브샘플링
#3. [H.264] Block-based Motion Estimation(ME)
#4. [H.264] Discrete Cosine Transform(DCT) 이산 코사인 변환
#5. [H.264] Quantization(양자화)과 Zig-zag scanning

안녕하세요? 맨날맑음 입니다.

가장 덥다는 말복이 바로 어제 였습니다. 다들 ‘삼계탕’은 맛있게 드셨는지 모르겠네요; 저는 이마트의 닭이 매진되어 삼계탕은 못 먹고 말았네요 ㅠ_ㅠ 그 큰 마트에서 매진이라니..말복 때 죽음을 맞이한 수많은 닭들에게 감사할 때 입니다;

이번 포스팅에서는 동영상 압축의 핵심이라 할 수 있는 Block-based Motion Estimation(이하 ME)에 관해 알아 보려고 합니다.

본 내용으로 들어가기 전에 ME에 관해 간단히 소개하자면, 지난 시간에 프레임과 그 인접한 프레임은 거의 비슷한 형태로 이루어 져 있다고 하였습니다. 만약 프레임1과 프레임2가 있을 때 프레임2는 1과 거의 비슷하기 때문에 굳이 모든 데이터를 가지고 있을 필요 없이, 1의 어느 부분과 비슷하다..라고 표시만 해주는 방법으로 데이터의 양을 줄이게 됩니다. 이렇게 하기 위해서 ME를 하여, 프레임1(Reference Frame) 에서 어느 부분과 가장 일치하는지 찾아주는 과정이라고 할 수 있습니다. 아래에서 자세히 알아보도록 하죠.

#1. Block-based?

위에서 Block-based Motion Estimation라고 했습니다. 굳이 번역하자면 블럭 기반의 움직임 추정(?)이라고 하면 될 것 같습니다. 그럼 블럭 기반이라는 말부터 살펴 보면 ME를 할때 프레임 전체를 한번에 하는 것이 아니라 하나의 프레임을 잘게 잘라(8×8, 16×16 or 32×32) 사용하게 됩니다. 기본적으로는 16×16의 매크로 블럭(Macro-Block)을 사용하게 됩니다.


-그림1. 16×16 Macro Block으로 나눈 모습-

#2. Motion Estimation



-그림2. Motion Estimation 개념도-

그림 2가 이해 가시나요?  Frame(t)(현재 프레임)에서 3번째 매크로 블럭을 처리하고 있다고 가정 합니다. Frame(t-1)(이전 프레임)에서 매크로 블럭과 가장 비슷한 곳을 찾는 모습이죠. 저 빨간색 사각형은 Frame(t-1)에서 비슷한 곳을 찾을 Search Range(검색 범위) 입니다. 눈으로 보아도 분홍색 화살표가 가르키고 있는곳이 현재 매크로 블럭과 많이 일치하는 것을 알 수 있습니다. Search Range는 임의로 정할 수 있지만 일반적으로 Block Size의 ±7을 사용하게 됩니다.

그럼 그림처럼 현재 매크로 블럭이 이전 프레임과 가장 일치하는 최고의 매칭 포인트를 어떻게 찾게 되는지 매우 궁금 해 집니다. 비밀은 바로 SAD 방정식에 있습니다. SAD 방정식을 사용하여 최고의 매칭 포인트를 찾아 내는 것이지요.


-그림3 SAD equation-

수식을 보니 갑자기 머리가 아파옵니다. 저 같이 수식 알러지가 있으신 분들을 위해 친절하게 그림으로 설명해 드리죠.갑자기 제가 친절한 금자씨(?)라도 된 것 같습니다;



 -그림4. Motion Estimation 과정(1)-

그림 4를 보면서 설명 하겠습니다. 이 그림은 이전 프레임(frame t-1)을 나타냅니다. 사각형 하나는 하나의 픽셀입니다. 빨간색 사각형으로 Search Range(검색 영역)가 있습니다. Cerrent block이 바로 현재 프레임의 매크로 블럭입니다. (원래 16x16으로 해야 하지만 그림 그리는 것도 만만치 않습니다)



 -그림5. Motion Estimation 과정(2)-


그림 5에서 보는 것 처럼 Search Range를 매크로 블럭으로 탐색 하면서 Frame(t-1) - Cerrent block 를 계산하여 그 ‘절대값’을 Origin에 저장하게 됩니다.



 -그림6. Motion Estimation 과정(3)-


이렇게 계산된 값들 중 그림 6에서 처럼 가장 작은 값을 찾는 것이죠. 숫자 22가 들어있는 좌표(6.5)가 최소값을 갖는 바로 Current Block과 가장 일치하는 이전 프레임의 좌표인 것입니다. 이 지점을 Motion Vector라고 합니다. 즉 이전 프레임에서 현재 블럭과 가장 일치하는 지점을 말합니다.



-그림7. Motion Vector-


이렇게 Search Range의 모든 좌표를 전부 검색하는 방법을 Full Search라고 합니다. 이러한 ME의 과정은 코덱이 영상을 압축하는 과정에서 많은 비트 수를 감소 시켜 주게 됩니다.  그림7의 단순한 프레임과의 차이와 ME를 사용한 차이를 보시면 확연하게 그 차이를 알 수 있습니다.(흰색이 데이터가 있는 부분입니다) ME를 했을 경우는 잔여 데이터가 거의 없는 것을 볼 수 있습니다.



-그림8. 단순한 프레임간의 차와 ME를 수행 했을 때의 차이-

 

그런데 ME는 전체 인코딩 과정중에 가장 많은 부하(?)를 일으킵니다. ME를 통해 데이터의 양은 많이 감소하게 되지만 Search를 하는 계산 과정이 있기 때문에 속도는 많이 떨어지게 되는 것이죠. 실제 H.264에서는 Full Search외에 여러 가지 Search 방법(예. 다이아몬드 서치)을 통해 속도 향상을 할 수 있도록 하고 있습니다.(이런 방법들은 차차 소개하도록 하겠습니다)

글이 많이 길어지는군요.. ME를 간단하게 요약 해 보자면.
  • 현재 프레임(t)의 처리 할 매크로 블락을 만든다.
  • 이전 프레임(t-1)에 Search Range를 설정한다.
  • Search Range를 SAD 방정식으로 Search 하여 그 결과 값을 저장한다.
  • 결과값 중에 가장 작은 값(Motion Vector)을 찾는다.
  • Moton Vector의 매크로 블럭과 현재 매크로 블럭의 차이의 절대값을 결과(Residual) 데이터에 저장한다. 


#3. 디코더(Decoder)의 데이터 복구

지금까지 인코더(Encoder) 측에서 ME를 통해 데이터를 줄이는 방법을 상세하게 설명 했습니다. 그렇다면 디코더에서는 어떻게 Residual 데이터를 가지고 원본 데이터를 복원해 나갈까요?


-그림9. 디코더는 어떻게 원본 이미지를 복원 할 수 있을까?-


정답은 ME의 과정을 반대로 수행 하면 될 것입니다. 디코더 또한 현재 프레임을 되 살릴 때 매크로 블럭 단위로 복원하게 됩니다. 그렇다면 디코더가 매크로 블럭을 복원하기 위해 가지고 있는 데이터는 무엇이 있을까요? 디코더는 바로 이전에 처리한 이전 프레임의 원본 이미지(사실 조금의 손실이 있는..)와 현재 프레임의 Residual 데이터를 가지고 있을 것 입니다. 이 두 가지를 가지고 현재 복원 할 매크로 블럭의 Residual 데이터와 이 Residual 데이터가 이전 프레임의 어디에 위치하였는지(Motion Vector)정보를 이용하여 둘을 합하여 현재 블럭을 복원 하는 것입니다. 그림 10과 같이 이러한 방법을 반복하여, 프레임 전체를 복원 하게 됩니다.



-그림10. 디코더의 이미지 복원 과정-
 


#4 . 실습

ME의 과정이 이해 가시나요? 설명 만으로는 100% 자신의 것으로 만들기 어렵습니다. C나 C++을 이용하여 프로그램을 만들어 보면 확실하게 이해가 될 것 입니다.

준비물.

  • 각자 익숙한 개발 툴(저는 Visual Studio 2008)
  • 실습에 필요한 YUV 파일 Download(http://trace.eas.asu.edu/yuv/)
    - 저는 football_sif.yuv 사용
  • 결과를 확인하기 위한 YUV 플레이어
    - 이 플레이어를 열고 마우스 오른쪽 버튼을 누른 후 셋팅에서 화면의 해상도와 Color 타입을 조정하여 사용하면 됩니다.

 

준비가 되었으면, ME를 작성 해 보시면 됩니다. 그런데 가장자리를 Search 하기 위해서는 Search Range가 –인덱스가 나오는 경우가 발생 하므로, 저는 학습의 편의상 동영상의 가장자리 16은 ME의 대상에서 제외 하도록 하였습니다.


아래에 제가 만들어본 프로그램을 올려 놓지만, 꼭 자신이 만들어 보아야 자신의 것이 됩니다.

프로그램을 컴파일 한 후, Debug 폴더안의 실행파일을 실행 시켜 ME를 수행 할 수 있으며, 결과는 Root 폴더의 Me_sample에서 residual.foo 파일을 열어 보면 확인 가능 합니다



#. 마치면서

이번 포스트에서는 동영상 압축의 핵심인 ME에 대한 자세한 소개와 디코더 쪽에서 데이터를 복원하는 방법을 알아 보았습니다. 다음번에는 DCT를 이용하여 데이터의 비트 수를 줄이는 방법에 대해 자세히 알아 보겠습니다.

Posted by 맨날맑음