#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 맨날맑음

댓글을 달아 주세요

  1. Favicon of http://dklee.net BlogIcon DKLEE 2009.08.15 09:35  댓글주소  수정/삭제  댓글쓰기

    안녕하세요 맨날 맑음님
    님의 부지런함이 결실 맺고 있는건지요^^?ㅎ
    잘됐음 좋겠어요!

  2. BGKim 2009.08.28 13:10  댓글주소  수정/삭제  댓글쓰기

    잘 정리 되어 있군요....ㅎㅎㅎ 늘 great mind 중의 한 사람이 되길 바랍니다.

  3. Favicon of http://blog.hoons.kr BlogIcon HOONS 2009.09.01 20:03  댓글주소  수정/삭제  댓글쓰기

    이론부터 차근차근 잘 설명해주셔서 많은것 배웠습니다. ( _ _)

  4. 초코미 2009.09.07 11:22  댓글주소  수정/삭제  댓글쓰기

    좋은 자료 잘 보고 갑니다.
    그동안 궁금했던 내용들이 다 있어서 감사한 마음에 한줄 남기고 갑니다.

    • Favicon of https://crynut84.tistory.com BlogIcon 맨날맑음 2009.09.07 12:39 신고  댓글주소  수정/삭제

      초코미님 안녕하세요?
      도움되셨다니 기뿌네요~^^
      요새 좀 게으름에 후속편들을 주닙 못하고 있는데요; 계속 이어지는 내용이니 계속 관심 부탁드립니다^^ 좋은하루 되세요

  5. 감탄 2009.09.07 17:10  댓글주소  수정/삭제  댓글쓰기

    프로그래밍과는 무관하게 영상을 하는 사람인데요 이것저것 궁금한 것들 찾다가 좋은 정보 얻어갑니다. 샘플링이나 RGB, YCbCr등 알고 싶었던 것들을 너무 쉽게 설명해 놓으셔서 잘 보고갑니다~

  6. Favicon of http://blog.naver.com/shine10ee BlogIcon 열이 2009.09.09 22:37  댓글주소  수정/삭제  댓글쓰기

    나도 이제 강의 들으면서 자료 좀 찾으려고 검색 해보니 여기가 들어와 지는군. ㅋㅋ

  7. 대단하시당 2009.11.02 16:16  댓글주소  수정/삭제  댓글쓰기

    만들어놓으신 ME압축파일 풀어봤는데
    "프로그램을 컴파일 한 후, Debug 폴더안의 실행파일을 실행 시켜 ME를 수행 할 수 있으며, 결과는 Root 폴더의 Me_sample에서 residual.foo 파일을 열어 보면 확인 가능 합니다 "
    파일이없던데요 ;;;;아쉽네요..

    • Favicon of https://crynut84.tistory.com BlogIcon 맨날맑음 2009.12.29 23:28 신고  댓글주소  수정/삭제

      네..YUV 파일 특성상 무압축 파일이기 때문에 크기가 큰 단점이 있습니다. 그로인해 업로드가 되지않아서 아쉽지만 소스코드만 올리게 되었습니다. 본문의 글중 해당 YUV 시퀀스를 검색하여 다운로드 하시고 소스를 돌리시면 결과를 보실 수 있습니다. 좋은하루 되세요~

  8. 찜배 2009.12.21 16:48  댓글주소  수정/삭제  댓글쓰기

    ㅋㅋㅋㅋ 나 지금 회사... 첫날이라 시키는것도 없고, 인터넷 하기는 민망하고, 공부라도 해야될꺼같아서 돌아다니는데, 맨날맑음이네,ㅋㅋㅋㅋㅋ

  9. scriptx 2010.01.15 09:01  댓글주소  수정/삭제  댓글쓰기

    얼핏보면 설명을 잘해놓은것 같지만 많이 부족하네요
    단순 프레임차이와 ME 적용했을때 용량차이가 하나도 나지 않네요.
    제대로 구현한게 맞긴 하나요?

    • Favicon of https://crynut84.tistory.com BlogIcon 맨날맑음 2010.01.15 13:18 신고  댓글주소  수정/삭제

      scriptx님 안녕하세요? 의견 감사합니다.

      코덱의 프로세싱에서 ME의 역할은 큰 비중을 차지 하게됩니다. 제가 아직 다음 포스팅을 쓰지 못하여 오해가 있으신것 같은데요.

      코덱의 프로세싱중 프레임간의 차이를 이용하는 Inter모드에서는 ME -> DCT -> Quantization -> Entropy coding의 과정을 거쳐야 실질적인 용량의 차이(압축)이 일어나게 됩니다.

      본 포스팅의 ME의 설명은 맞는것이구요. 좀더 정확히 하자면 소스코드에서 구현은 Y(Luminance)성분만 이용했지만, 실제 코덱은 UV(Chrominance)성분까지 ME의 과정을 거치게 됩니다.

      지금 DCT,Quantization 관련 포스팅을 준비중에 있으니 계속 관심 가져 주시면 좋겠습니다 좋은하루되세요^^

  10. 서준현 2010.04.05 20:51  댓글주소  수정/삭제  댓글쓰기

    궁금증이 허접하지만... 못참고 글을 올립니다...^^
    SAD방정식에서 시그마로 인해 변하는 값은 x축인데...
    갑자기 y축이 변하는 그림이 보이는데...뭘 의미하는지 이해가 안가서요..
    ㅠㅠ

  11. 시커먼스 2010.05.03 13:28  댓글주소  수정/삭제  댓글쓰기

    이해가 쏙쏙 되는 설명이네요~ㅋ
    그럼 가장자리 16픽셀만큼의 블락들은 어떻게 처리해야 되나요?

    • 오래전에 2010.06.16 17:52  댓글주소  수정/삭제

      오래전에 공부해서 잘 기억은 나지 않지만,, Edge를 처리하는 방법이 따로 있는것으로 기억합니다. H.263이 기본적인 개념을 이해하는데 도움이 되었던 것 같에요. H.264에 대한 Standard를 보시는 것도 도움이 될 것이라 생각됩니다.

  12. 젤리 2010.05.27 15:48  댓글주소  수정/삭제  댓글쓰기

    안녕하세요. 저도 영상압축을 공부하는 학도입니다.여러가지 유익한 정보 감사드립니다. 한가지 부탁이 있습니다. YUV시퀀스 파일을 다운로드 할수 있는 사이트를 좀 가르쳐주시면 안될까요?? 검색을 못하겠어요 ㅠㅠ

  13. 영상초보 2010.06.14 21:01  댓글주소  수정/삭제  댓글쓰기

    감사합니다 유익한 정보 감사합니다. 한가지 궁금한 점이 있는데요 단지 motion compensation한 영상을 뿌려주면 그게 동영상이 되는 건가요?

  14. 학생 2011.10.15 23:58  댓글주소  수정/삭제  댓글쓰기

    그림 7과 그림 8사이에

    [ '그림7'의 단순한 프레임과의 차이와 ME를 사용한 차이를 보시면 확연하게 그 차이를 알 수 있습니다. ]
    에서 그림 8로 고쳐야 할것 같아요 ! 헷갈리신듯 ㅋ
    저도 한참 헤맸네요 ㅠ

    공부 많이 하고 갑니다 !!! 정말 도움이 많이 되었네요, 감사합니다 !

  15. Favicon of http://mih.christianlouboutinouts.com/ BlogIcon christian louboutin pas cher 2013.04.08 08:26  댓글주소  수정/삭제  댓글쓰기

    다른 남자 부르면서 울거면 나한테 이쁘지나 말던지

  16. ees15322 2015.06.20 16:19  댓글주소  수정/삭제  댓글쓰기

    츤데레

  17. 2015.07.09 11:42  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다