[Motion Estimation] Diamond Search Algorithm

  
 Diamond Search 알고리즘은 다음 그림 3>과 같이 가운데 블록을 중심으로 상, 우상, 우, 우하, 하, 좌하, 좌, 좌상의 9개 블록을 비교하여 MAD값을 각각 추출하며(Large Diamond Search Pattern: LDSP), MAD값이 가장 작은 블록을 중심으로 다시 탐색을 하게 된다. 

 만일 가운데 값이 가장 작은 블록일 경우에는 그 블록을 중심으로 상, 하, 좌, 우 포함 5개 블록만을 비교하며(Small Cross Search Pattern or Small Diamond Search Pattern: SCSP), 이 두번째 조건에서도 가운데 값이 가장 작을 경우 그 블록의 Motion Vector를 추출하게 된다.

 또한 LDSP의 다이아몬드 형태 이동 시 우상, 좌상, 우하, 좌하의 대각선 움직임 시에는 중심값 이동 후 수평, 수직, 그 사이값의 세개의 블록만 탐색하며, 상, 하, 좌, 우의 움직임 시에는 같은 맥락으로 중심값 이동후 5개의 블록만 탐색하게 된다. 
 다음으로 SCSP의 작은 다이아몬드 형태 이동시에도 세개의 블록만 탐색하므로, 빠른 속도를 발휘 할 수 있다.

마지막으로 Early Point를 설정하여 알고리즘의 루프를 보다 빠르게 탈출하도록 유도 하였다. 구하길 원하는 MAD값의 최소값을 Critical PEL이란 이름으로 지정하여, Critical PEL보다 작은 MAD값이 구해질 경우 바로 탈출하게 하여, 너무 미세한 MAD값은 구하지 않도록 하였다.

본 방법을 통하여 Full Search 알고리즘과 비교했을 때 약 10배 이상 처리 속도를 구현할 수 있었다.








※ MAD 계산
 MAD(Mean Absolute Differnce)값의 계산은 블록과 그에 상응하는 프레임의 각 픽셀값의 차를 구하고 절대값으로 처리하여 16x16 픽셀 전체의 합을 구한다. 이 값이 절대차의 합 MAD값이 된다.

소스 코드 :
 1static Int MAD(Uint8 *blk1, Uint8 *blk2, Int distlim)
2...{
3    Int i,j;
4    Int s=0;
5    for(j=0;j<BLOCK_SIZE; j++)
6    ...{
7        for(i=0;i<BLOCK_SIZE;i++)
8        ...{
9            s+=unsign(blk1[i]-blk2[i]);
10        }       
11        if(s>= distlim)
12            break;       
13        blk1+=PROVE_HSIZE;
14        blk2+=PROVE_HSIZE;       
15    }
16    return s;
17}




※ Full Search Algorithm
 Full Search 알고리즘은 MPEG-2 인코딩에 사용된 Motion Estimation의 기본 알고리즘이다. Search 방식은 블록마다 정해진 영역이내의 모든 블록만큼의 MAD값을 구하고 가장 작은 MAD값을 가진 블록을 추출하는 것이다.
 각 블록의 MAD추출 호출 순서는 스파이럴(Spiral) 방식으로서 중심에서 시작해 이동 반경을 넓혀가며 오른쪽으로 이동, 위로 이동, 왼쪽으로 이동, 아래로 이동을 반복하며 탐색한다. 이러한 순서를 지켜가며 블록단위마다 MAD값을 구해낸다. 하지만, MAD값이 0인 정확히 일치하는 블록이 없을 경우에는 지정된 영역 전체를 탐색해야 하므로 상대적으로 비효율적인 속도를 보여준다.